PAT--L2-013. 红色警报

╰半橙微兮° 2022-06-13 02:26 163阅读 0赞

题目链接：[https://www.patest.cn/contests/gplt/L2-013][https_www.patest.cn_contests_gplt_L2-013]

题目描述：

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的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.

很明显这是一个图的问题，将题中给出的数据在草稿纸上画出来就是一个图：

![这里写图片描述][SouthEast]

圆中的数字代表图的顶点编号，按照题中说的意思，如果某个城市被攻占（这个城市对应图顶点和其他图顶点之间的边被删除），会使得图的连通子图增加 2 个或者 2 个以上的话，那么发出红色警报，否则不发警报，举个例子，如果一开始顶点 1 被攻占，那么顶点 1 和其他顶点之间的边被删除，原图变成了下面的图：

![这里写图片描述][SouthEast 1]

原来的图有 2 个连通子图，现在的图有 3 个连通子图。只增加了一个连通子图，因此这时不发警报。  
同样的，当顶点 2 所代表的城市被攻占了之后，图的连通子图个数不变，也不发出警报。  
当顶点 0 所代表的的城市被攻占了之后，整个图就变成了完全不连通的：

![这里写图片描述][SouthEast 2]

这个时候的连通子图个数就变成了 5 个，比原来增加了两个，因此此时发出红色警报。

既然这样的话我们就能想出大概的思路了：当一个城市被攻占之后，只要对比当前的连通子图个数和上一次连通子图的个数就可以判断了。这个我们可以通过图的遍历来解决，那么什么时候 Game Over 呢？当所有的城市都被攻占之后：我们可以用一个标记数组来表示城市的状态，当所有的城市都被标记了攻占的时候结束。下面是代码：

#include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    const int N = 505, M = 5005;
    // 图的邻接矩阵 
    int edge[N][N];
    // 遍历图的标记数组 
    bool isVisit[N]; 
    // 标记城市的状态：(0: 未被攻占，-1: 被攻占) 
    int city[N];
    int n, m, k;
    
    // 从顶点 x 开始深度优先遍历其所在的连通图 
    void dfs(int x) {
        if(isVisit[x]) {
            return ;
        }
        isVisit[x] = true;
        for(int i = 0; i < n; i++) {
            if(edge[x][i] == 1) {
                dfs(i);
            }
        }
    }
    
    int main() {
        // 当前图的连通子图个数 
        int counnt = 0;
        cin >> n >> m;
        int s, e;
        // 邻接矩阵初始化 
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &s, &e);
            edge[s][e] = edge[e][s] = 1;
        }
        // 对所有的顶点都遍历一次，求出当前图的连通子图个数 
        for(int i = 0; i < n; i++) {
            // 如果顶点 i 未被访问，证明顶点 i 在一个新的连通子图中 
            if(!isVisit[i]) {
                dfs(i);
                counnt++;
            }
        }
        // lastCount 记录图的上一次状态时的连通子图个数 
        int x, lastCount;
        cin >> k;
        for(int i = 0; i < k; i++) {
            scanf("%d", &x);
            // 城市 x 被攻占，标记 
            city[x] = -1;
            // 删除被攻占城市和其他城市的边 
            for(int j = 0; j < n; j++) {
                if(edge[j][x] == 1) {
                    edge[j][x] = edge[x][j] = 0;
                }
            }
            // 初始化顶点访问标记用于求出图的连通子图个数 
            memset(isVisit, 0, sizeof(isVisit));
            lastCount = counnt;
            counnt = 0; 
            for(int j = 0; j < n; j++) {
                if(!isVisit[j]) {
                    dfs(j);
                    counnt++;
                }
            }
            // 如果连通子图的个数相比上一次增加了 2 个或者两个以上，发出红色警报 
            if (lastCount + 2 <= counnt) {
                printf("Red Alert: City %d is lost!\n", x);
                // 这里调用了 algorithm 中的函数 count，求出给定范围中给定的值的个数，这里表示所有城市都被攻占 
            } else if(count(city, city+n, -1) == n){
                printf("City %d is lost.\n", x);
                printf("Game Over.\n");
                return 0;
            } else {
                printf("City %d is lost.\n", x);
            }
        }
    
        return 0;
    }

[https_www.patest.cn_contests_gplt_L2-013]: https://www.patest.cn/contests/gplt/L2-013
[SouthEast]: /images/20220613/31f9509bf03541428a29b9640229e6b8.png
[SouthEast 1]: /images/20220613/24edf6945a4f46cfab10c5a4a7937400.png
[SouthEast 2]: /images/20220613/8aa2d45ce3214fde82c6f3e1ea2e7ad4.png