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

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cmath>
 5 #include <cstring>
 6 using namespace std;
 7 int n,m;
 8 struct node
 9 {
10     int u,v;
11 } e[5005];
12 int vist[550],fa[550];
13 int Find(int x)
14 {
15     return x==fa[x]?fa[x]:Find(fa[x]);
16 }
17 void Union(int x,int y)
18 {
19     int xc=Find(x);
20     int yc=Find(y);
21     if(xc!=yc)
22     {
23         fa[xc]=yc;
24     }
25 }
26 int main()
27 {
28     int k;
29     int u,v;
30     while(scanf("%d%d",&n,&m)!=EOF)
31     {
32         for(int i=0; i<n; i++)
33             fa[i]=i;
34         for(int i=0; i<m; i++)
35         {
36             scanf("%d%d",&u,&v);
37             e[i].u=u,e[i].v=v;
38             Union(u,v);
39         }
40         int num=0,num1;
41         for(int i=0; i<n; i++)
42         {
43             if(fa[i]==i)
44             {
45                 num++;
46             }
47         }
48         memset(vist,0,sizeof(vist));
49         scanf("%d",&k);
50         while(k--)
51         {
52             num1=0;
53             for(int i=0;i<n;i++)
54                 fa[i]=i;
55             int x;
56             scanf("%d",&x);
57             vist[x]=1;
58             for(int i=0;i<m;i++)
59             {
60                 if(vist[e[i].u]==1||vist[e[i].v]==1)
61                 continue;
62                 else
63                     Union(e[i].u,e[i].v);
64             }
65             for(int i=0;i<n;i++)
66                 if(fa[i]==i)
67                 num1++;
68             if(num==num1||num+1==num1)
69             printf("City %d is lost.
",x);
70             else
71                 printf("Red Alert: City %d is lost!
",x);
72             num=num1;
73         }
74         num=0;
75         for(int i=0;i<n;i++)
76             if(vist[i]==1)
77             num++;
78         if(num==n)
79             printf("Game Over.
");
80     }
81     return 0;
82 }