【PTA】7-39 红色警报

男娘i 2023-07-03 07:21 27阅读 0赞

#### 题目重述 ####

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

#### C++ AC ####

#include<iostream>
    #include<bits/stdc++.h>
    # define MAX 505
    using namespace std;
    int n, m;
    int pre[MAX];//并查集数组
    bool vis[MAX];//判断是否已经被攻占
    pair<int, int> P[5005];//保存初始的连通信息
    //初始化并查集
    void init()
    {
        
        for (int i = 0; i < n; i++)
        {
        
            pre[i] = i;
        }
    }
    //并查集的查找
    int Find(int x)
    {
        
        if (pre[x] != x) return Find(pre[x]);
        return x;
    }
    //并查集的合并
    void merge2(int x, int y)
    {
        
        int fx = Find(x);
        int fy = Find(y);
        if (fx != fy)
        {
        
          pre[fx] = fy;
        }
    }
    int main()
    {
        
        memset(vis, false, sizeof(vis));
        cin>>n>>m;
        init();
        for (int i = 0; i < m; i++)
        {
        
            cin>>P[i].first>>P[i].second;
            merge2(P[i].first, P[i].second);
        }
        int cnt = 0;
        //初始连通的区域数
        for (int i = 0; i < n; i++)
        {
        
            if (pre[i] == i)
            {
        
                cnt++;
            }
        }
        int k,u;
        cin>>k;
        for (int t = 0; t < k; t++)
        {
        
    
            cin>>u;
            vis[u] = true;
            init();
            for (int i = 0; i < m; i++)
            {
        
                int x = P[i].first, y = P[i].second;
                if (!vis[x] && !vis[y])
                {
        
                     merge2(x, y);
                }
            }
            int cur = 0;
            //在这个城市被攻陷后的连通区域
            for (int i = 0; i < n; i++)
            {
        
                if (!vis[i] && pre[i] == i)
                {
        
                      cur++;
                }
            }
    
            if (cur + 1 == cnt || cur == cnt)//本来就是一个独立的连通区域丢失(并不会影响连通性) 或者没有改变其他结点的连通性
            {
        
                printf("City %d is lost.\n", u);
            }
            else
            {
        
                 printf("Red Alert: City %d is lost!\n", u);
            }
            //更新连通区域数
            cnt = cur;
        }
        if (k == n)
        {
        
            printf("Game Over.\n");
        }
        return 0;
    }