题意:
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的 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、并查集判连通,若城市被攻占,则不加入并查集。
2、连通块个数增加,发出红色警报。
- #include<bits/stdc++.h>
- using namespace std;
- const double eps = 1e-8;
- const int MAXN = 500 + 10;
- const int MAXT = 5000 + 10;
- int fa[MAXN];
- int vis[MAXN];
- int v[MAXN];
- int Find(int x){
- return fa[x] = (fa[x] == x) ? x : Find(fa[x]);
- }
- void init(){
- for(int i = 0; i < MAXN; ++i){
- fa[i] = i;
- }
- }
- struct Edge{
- int from, to;
- void read(){
- scanf("%d%d", &from, &to);
- }
- }num[MAXT];
- int main(){
- int n, m;
- scanf("%d%d", &n, &m);
- init();
- for(int i = 0; i < m; ++i){
- num[i].read();
- int x = num[i].from;
- int y = num[i].to;
- v[x] = 1;
- v[y] = 1;
- int tmpx = Find(x);
- int tmpy = Find(y);
- if(tmpx == tmpy) continue;
- if(tmpx < tmpy){
- fa[tmpy] = tmpx;
- }
- else{
- fa[tmpx] = tmpy;
- }
- }
- int cnt = 0;
- for(int i = 0; i < n; ++i){
- if(!v[i]) continue;
- if(fa[i] == i){
- ++cnt;
- }
- }
- int w = n;
- int k;
- scanf("%d", &k);
- while(k--){
- int t;
- scanf("%d", &t);
- vis[t] = 1;
- --w;
- if(w == 0){
- printf("City %d is lost.\n", t);
- printf("Game Over.\n");
- break;
- }
- init();
- for(int i = 0; i < m; ++i){
- int x = num[i].from;
- int y = num[i].to;
- if(vis[x] || vis[y]) continue;
- int tmpx = Find(x);
- int tmpy = Find(y);
- if(tmpx == tmpy) continue;
- if(tmpx < tmpy){
- fa[tmpy] = tmpx;
- }
- else{
- fa[tmpx] = tmpy;
- }
- }
- int tmp = 0;
- for(int i = 0; i < n; ++i){
- if(!v[i]) continue;
- if(vis[i]) continue;
- if(fa[i] == i) ++tmp;
- }
- if(tmp > cnt){
- printf("Red Alert: City %d is lost!\n", t);
- }
- else{
- printf("City %d is lost.\n", t);
- }
- cnt = tmp;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1989656.html