【CCCC】L2-013 红色警报 (25分)，，并查集计算集合个数

problem

L2-013 红色警报 (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.。

输入样例：
5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3
输出样例：
City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.
作者
陈越
单位
浙江大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

• n个点m条边的图，随后按顺序割掉k个点，每次判断剩余图的连通性

solution

• 连通性，很容易想到并查集
• 每攻打一次城市重新跑一次并查集（不合并已经被攻打的点），如果当前集合个数与上一张图的集合数相等或者+1则无影响，否则红色警告。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5050;

int x[maxn], y[maxn], vis[maxn];

int fa[maxn];
void init(int n){for(int i = 0; i < n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){//统计并查集集合个数
	int cnt = 0;
	for(int i = 0; i < n; i++)//节点从0-n编号
		if(fa[i]==i)cnt++;
	return cnt;
}

int main(){
	int n, m;
	cin>>n>>m;
	init(n);
	for(int i = 1; i <= m; i++){
		cin>>x[i]>>y[i];
		merge(x[i],y[i]);
	}
	int k;  cin>>k;
	int cc1=count(n), cc2;
	for(int i = 1; i <= k; i++){
		int t;  cin>>t;
		vis[t] = 1;//被攻占的不再联通
		init(n);
		for(int j = 1; j <= m; j++){
			if(vis[x[j]]||vis[y[j]])continue;
			merge(x[j],y[j]);
		}
		cc2 = count(n);
		//cout<<cc2<<endl;
		if(cc2==cc1||cc2==cc1+1)
			printf("City %d is lost.\n",t);
		else 
			printf("Red Alert: City %d is lost!\n",t);
		cc1 = cc2;
	}
	if(k==n)printf("Game Over.\n");
	return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/108913074