团体程序设计天梯赛-练习集 L2-013 红色警报 (25分) 题目解析并查集做法

谁践踏了优雅 2023-10-11 15:03 22阅读 0赞

### 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.

> 本题思路：采用并查集的思想解答，每次攻占一个城市，和其关联的城市不再建立连通关系（注：这里采用结构体存储道路两端的城市的编号），最后就是对新建立的连通集的连通个数与原来的连通集的连通个数进行判断即可。

判断新建连通集的连通个数与原来的连通集的连通个数时，  
如果连通个数不变（攻占本来就不连通的城市），或者连通个数比原来多一（攻占与其他城市连通的城市，因为只是攻占的城市被单独出来，因此连通集个数会多一）时，不发生红色警报。  
如果说攻占的城市导致连通性发生改变那么整体新建立的连通集个数至少比原来多2个！会发生红色警报，因此在后面就好判断了

#include<bits/stdc++.h>
    #define Inf 0x3f3f3f
    const int N = 505;
    using namespace std;
    
    struct edge{
        
    	int x;
    	int y;
    }edge[N*10];
    int city[N], pre[N];
    int n, m, k, sum;
    bool visit[N] = {
        false};
    
    void init(int n){
        
    	for(int i = 0; i < n; i ++)
    		pre[i] = i;
    }
    
    int SearchRoot(int root){
        //查找祖先节点
    	while(root != pre[root])
    		root = pre[root];
    	return root;
    }
    
    void join(int a1, int a2){
        
    	int roota1 = SearchRoot(a1);
    	int roota2 = SearchRoot(a2);
    	if(roota1 != roota2)//建立连通关系
    		pre[roota1] = pre[roota2];
    }
    
    int main(){
        
    	int c1, c2;
    	cin >> n >> m;
    	init(n);//初始化
    	for(int i = 0; i < m; i ++){
        
    		cin >> c1 >> c2;
    		edge[i].x = c1;
    		edge[i].y = c2;
    		join(c1, c2);
    	}
    	for(int i = 0; i < n; i ++)
            if(pre[i] == i)
            	sum++;
            	
    	cin >> k;
    	for(int i = 0; i < k; i ++){
        
    		int ans, cnt = 0;
    		cin >> ans;
    		visit[ans] = true;//标记被攻占
    		init(n);//重新初始化得到当前连通个数
    		for(int i = 0; i < m; i ++){
         //所有道路中，与ans城市有关的道路不在建立
    			if(visit[edge[i].x] || visit[edge[i].y])
    				continue;
                join(edge[i].x, edge[i].y);//重新建立连通集
    		}
    		for(int i = 0; i < n; i ++)//遍历当前连通集的连通个数
    			if(pre[i] == i)
    				cnt++;
            if(sum==cnt-1 || sum==cnt)//如果当前连通个数=原来的连通个数，或者比原来的连通个数多一个
                printf("City %d is lost.\n", ans);
    		else
    			printf("Red Alert: City %d is lost!\n", ans);
    		sum = cnt;
    	}
    	if(k>=n)
    		printf("Game Over.\n");
    	return 0;
    }