城市连通性判断程序：道路破坏后的连通性分析

#include #include #include using namespace std; int v[510]; int per[510]; struct Edge { int a,b; }e[5005]; int find(int t) { return v[t]==t?t:v[t]=find(v[t]); } void Union(int x,int y) { int p1=find(x); int p2=find(y); if(p1!=p2) v[p1]=p2; } int count(int z) { int counts=0; for(int i=0;i<z;i++) if(v[i]==i) counts++; return counts; } void INI() { for(int i=0;i<510;i++)
v[i]=i; } int main() { INI(); memset(per,0,sizeof(per)); int n,m,k; cin>>n>>m; for(int i=0;i<m;i++) { scanf("%d%d","&e[i].a,&e[i].b); Union(e[i].a,e[i].b); } int c1=count(n); cin>>k; for(int j=0;j<k;j++) { int c2=0; int p; cin>>p; per[p]=1; INI(); for(int i=0;i<m;i++) { if(per[e[i].a]==1||per[e[i].b]==1) continue; Union(e[i].a,e[i].b); } c2=count(n); if(c1+1 == c2||c1 ==c2) printf("City %d is lost.\n",p); else printf("Red Alert: City %d is lost!\n",p); c1 = c2; } c1=count(n); if(c1==n) printf("Game Over.\n"); return 0; }