7-21 红色警报 (25分)
题目
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的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.。
输入样例：
1 | 5 4 |
2 | 0 1 |
3 | 1 3 |
4 | 3 0 |
5 | 0 4 |
6 | 5 |
7 | 1 2 0 4 3 |
输出样例：
1 | City 1 is lost. |
2 | City 2 is lost. |
3 | Red Alert: City 0 is lost! |
4 | City 4 is lost. |
5 | City 3 is lost. |
6 | Game Over. |
代码
1 | |
2 | using namespace std; |
3 | int f[6000]; |
4 | int vis[10000]={0}; |
5 | struct fun{ |
6 | int x,y; |
7 | }great[10000]; |
8 | int find(int x){ |
9 | if(x!=f[x]){ |
10 | return find(f[x]); |
11 | } |
12 | return x; |
13 | } |
14 | void marge(int x,int y){ |
15 | int fx=find(x); |
16 | int fy=find(y); |
17 | if(fx!=fy){ |
18 | f[fy]=fx; |
19 | } |
20 | } |
21 | void init(){ |
22 | for(int i=0;i<6000;i++){ |
23 | f[i]=i; |
24 | } |
25 | } |
26 | int main(){ |
27 | init(); |
28 | int n,m,a,b; |
29 | scanf("%d %d",&n,&m); |
30 | for(int i=0;i<m;i++){ |
31 | scanf("%d %d",&a,&b); |
32 | great[i].x=a; |
33 | great[i].y=b; |
34 | marge(a,b); |
35 | } |
36 | int num=0; |
37 | for(int i=0;i<n;i++){ |
38 | if(f[i]==i){ |
39 | num++; |
40 | } |
41 | } |
42 | int t; |
43 | scanf("%d",&t); |
44 | for(int i=0;i<t;i++){ |
45 | scanf("%d",&a); |
46 | init(); |
47 | vis[a]=1; |
48 | int num1=0; |
49 | for(int i=0;i<m;i++){ |
50 | if(vis[great[i].x]!=1&&vis[great[i].y]!=1){ |
51 | marge(great[i].x,great[i].y); |
52 | } |
53 | } |
54 | for(int i=0;i<n;i++){ |
55 | if(f[i]==i){ |
56 | num1++; |
57 | } |
58 | } |
59 | if(num1==num||num1==num+1){ |
60 | printf("City %d is lost.\n",a); |
61 | } |
62 | else{ |
63 | printf("Red Alert: City %d is lost!\n",a); |
64 | } |
65 | num=num1; |
66 | } |
67 | if(t==n){ |
68 | printf("Game Over.\n"); |
69 | } |
70 | return 0; |
71 | } |