Life has its own fate, and meeting may not be accidental.

0%

pta-7-21 红色警报 (25分)(并查集)

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
#include<bits/stdc++.h>
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
}