L2-013. 红色警报（并查集）*

L2-013. 红色警报

参考博客

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 #include <cstring>

 using namespace std;

 int n,m;

 struct node

 {

     int u,v;

 } e[];

 int vist[],fa[];

 int Find(int x)

 {

     return x==fa[x]?fa[x]:Find(fa[x]);

 }

 void Union(int x,int y)

 {

     int xc=Find(x);

     int yc=Find(y);

     if(xc!=yc)

     {

         fa[xc]=yc;

     }

 }

 int main()

 {

     int k;

     int u,v;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         for(int i=; i<n; i++)

             fa[i]=i;

         for(int i=; i<m; i++)

         {

             scanf("%d%d",&u,&v);

             e[i].u=u,e[i].v=v;

             Union(u,v);

         }

         int num=,num1;

         for(int i=; i<n; i++)

         {

             if(fa[i]==i)

             {

                 num++;

             }

         }

         memset(vist,,sizeof(vist));

         scanf("%d",&k);

         while(k--)

         {

             num1=;

             for(int i=;i<n;i++)

                 fa[i]=i;

             int x;

             scanf("%d",&x);

             vist[x]=;

             for(int i=;i<m;i++)

             {

                 if(vist[e[i].u]==||vist[e[i].v]==)

                 continue;

                 else

                     Union(e[i].u,e[i].v);

             }

             for(int i=;i<n;i++)

                 if(fa[i]==i)

                 num1++;

             if(num==num1||num+==num1)

             printf("City %d is lost.\n",x);

             else

                 printf("Red Alert: City %d is lost!\n",x);

             num=num1;

         }

         num=;

         for(int i=;i<n;i++)

             if(vist[i]==)

             num++;

         if(num==n)

             printf("Game Over.\n");

     }

     return ;

 }