这道题是简易版的top1001，需要做的就是在去掉一个城市后，数剩下的联通块个数，DFS可解。
#include <stdio.h> #include <iostream> #include <string.h> using namespace std; #define MAX 1005 int Map[MAX][MAX]; int visit[MAX]; int N,M,K; void Remove(int node) { visit[node] = -1; } void DFS(int node, int label) { if(node > N) return; for(int i = 1 ; i <= N ; i ++) { if(visit[i] ==0 && Map[node][i] == 1) { visit[i] = label; DFS(i, label); } } } int main() { int a , b ; cin >> N >> M >> K; memset(Map, 0 , sizeof(Map)); for(int i = 0 ; i < M ; i ++) { cin >> a >> b; Map[a][b] = 1; Map[b][a] = 1; } int ans , city ; for(int i = 0 ; i < K ; i ++) { memset(visit, 0 , sizeof(visit)); cin >> city ; Remove(city); ans = 1 ; for(int i = 1 ; i <= N ; i ++) { if(visit[i] == 0) { DFS(i, ans); ans ++ ; } } cout << ans - 2 << endl; } return 0; }