战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
输入格式： 输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤ 5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。
注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。
输出格式： 对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。
输入样例：
5 4 0 1 1 3 3 0 0 4 5 1 2 0 4 3输出样例：
City 1 is lost. City 2 is lost. Red Alert: City 0 is lost! City 4 is lost. City 3 is lost. Game Over. DFS #include <cstdio> #include <algorithm> using namespace std; bool visit[510]; int e[510][510], n, m, k; void dfs(int node) { visit[node] = true; for(int i = 0; i < n; i++) { if(visit[i] == false && e[node][i] == 1) dfs(i); } } int dfstrave() { int cnt = 0; fill(visit, visit + 510, false); for(int i = 0; i < n; i++) { if(visit[i] == false) { dfs(i); cnt++; } } return cnt; } int main() { scanf("%d%d", &n, &m); int a, b, city; for(int i = 0; i < m; i++) { scanf("%d%d", &a, &b); e[a][b] = e[b][a] = 1; } scanf("%d", &k); int cnt=dfstrave(); for(int i = 0; i < k; i++) { scanf("%d", &city); for(int j = 0; j < n; j++) { if(e[city][j] == 1) { e[city][j] = 0; e[j][city] = 0; } } int tempcnt = dfstrave(); if(tempcnt > cnt+1){ printf("Red Alert: City %d is lost!\n", city); } else printf("City %d is lost.\n", city); cnt = tempcnt; if(i == n - 1) printf("Game Over.\n"); } return 0; } 并查集 #include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<map> #include<list> #include<set> #include<cmath> using namespace std; typedef long long ll; #define N 505 int edge[N][N],vis[N]; int fa[N],lost[N]; int find(int x){ if(fa[x]==x) return x; return fa[x] = find(fa[x]); } int Union(int x,int y){ int rx = find(x),ry=find(y); if(rx!=ry) fa[ry]=rx; } int count(int n){ int res = 0; for(int i=0;i<n;i++) if(fa[i]==i) res++; return res; } void init(){ for(int i=0;i<=N;i++) fa[i] = i; } int main(){ int n,m,x,y; cin >> n >> m; int con[m][2]; init(); for(int i=0;i<m;i++){ scanf("%d%d",&con[i][0],&con[i][1]); edge[con[i][0]][con[i][1]] = 1;edge[con[i][1]][con[i][0]] = 1; Union(con[i][0],con[i][1]); } int t,cnt0 = count(n); cin >> t; while(t--){ cin >> x; lost[x] = 1; init(); for(int i=0;i<m;i++){ if(lost[con[i][0]]||lost[con[i][1]]) ; else Union(con[i][0],con[i][1]); } int cnt = count(n); if(cnt==cnt0+1||cnt<=cnt0) printf("City %d is lost.\n",x); else printf("Red Alert: City %d is lost!\n",x); cnt0 = cnt; } if(cnt0==n) printf("Game Over.\n"); return 0; } BFS #include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<queue> using namespace std; typedef long long ll; #define N 505 int edge[N][N],vis[N],lost[N],n; queue<int> qu; void bfs(int i){ vis[i]=1; qu.push(i); while(qu.size()){ int e = qu.front(); vis[e] = 1; qu.pop(); for(int i=0;i<n;i++){ if(edge[e][i]&&!vis[i]) { qu.push(i); vis[i]=1; } } } } int main(){ int m,x,y,t,precnt=0,cnt=0; cin >> n >> m; for(int i=0;i<m;i++){ cin >> x >> y; edge[x][y] = 1;edge[y][x] = 1; } for(int i=0;i<n;i++){ if(!vis[i]) { bfs(i); precnt ++; } } cin >> t; for(int k=0;k<t;k++){ memset(vis,0,sizeof(vis)); cnt = 0; cin >> x; for(int j=0;j<n;j++){ if(edge[x][j]==1){ edge[x][j]=0; edge[j][x]=0; } } for(int i=0;i<n;i++){ if(!vis[i]){ bfs(i); cnt++; } } if(cnt<=precnt+1) printf("City %d is lost.\n",x); else printf("Red Alert: City %d is lost!\n",x); precnt = cnt; if(k==n-1) printf("Game Over.\n"); } return 0; }