战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的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.
#include <bits/stdc++.h> using namespace std; int e[550][550]; int f[550]; int gef(int v) { if(f[v]==v) return v; f[v]=gef(f[v]); return f[v]; } void mager(int a,int b) { int t1,t2; t1=gef(a); t2=gef(b); if(t1!=t2) { f[t2]=t1; } } int main() { int n,m,i,u,v,k,j,l,sum=0; int b[550]; scanf("%d %d",&n,&m); for(i=1; i<=m; i++) { scanf("%d %d",&u,&v); e[u][v]=e[v][u]=1; } scanf("%d",&k); for(i=0; i<n; i++) { f[i]=i; b[i]=-1; } int sum1,sum2; for(i=0; i<n-1; i++) { for(j=i+1; j<n; j++) { if(e[i][j]==1) mager(i,j); } } sum1=0; for(i=0; i<n; i++) if(f[i]==i) sum1++; /* sum1,表示失去节点u前n个城市被分为的部分的数目 sum2,表示失去节点u后n个城市被分为的部分的数目 sum,记录已经失去的节点的数目 b数组，标记节点(城市)i是否已经失去 */ for(l=1; l<=k; l++) { sum2=0; scanf("%d",&u); if(b[u]==-1) { b[u]=1; sum++; } for(i=0; i<n; i++) e[u][i]=e[i][u]=0; for(i=0; i<n; i++) f[i]=i; for(i=0; i<n-1; i++) { for(j=i+1; j<n; j++) { if(e[i][j]==1) mager(i,j); } } for(i=0; i<n; i++) if(f[i]==i) sum2++; if(sum2>sum1+1) printf("Red Alert: City %d is lost!\n",u); else printf("City %d is lost.\n",u); sum1=sum2; if(sum==n) { printf("Game Over.\n"); break; } } return 0; }