并查集+建图同样是逆向思维和星球大战类似

fyjie / 2024-02-26 / 原文

L2-013 红色警报

分数 25

作者陈越

单位浙江大学

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。

意思就是1个连通块，如果删掉x后就出现多个连通块了，那就是红色警报。如果删除x后，连通块个数不变，那是普通警报（不要发出警报，下面写成普通警报了，没办法了）

比如1 - 0 - 3 删除0 发出红色警报 1-0-3删除1发普通警报

输入格式：

输入在第一行给出两个整数N（0

注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。

输出格式：

对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。

输入样例：

输出样例：

City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.

连通状态用并查集表示，并查集没法删除元素，

采用逆向思维，从全摧毁开始一个一个恢复，全摧毁时的状态反应了摧毁第destory[k-1]个城市后的情况（摧毁是一个连续的过程，摧毁第destory[k-1]个意味着k-1前面的都以摧毁），恢复destory[k-1]城市后的连通状态是摧毁destory[k-2]城市的情况，恢复destory[1]城市后是摧毁destory[0]城市的情况,恢复destory[0]后是所有城市的连通状态。

恢复一个城市就遍历该点的邻居，并记录与该城市连接的连通块个数，

如果>1，那该破坏的城市就连接了多个连通块，也就是题目中的红色警报。(单点也算一个连通块)

如果=1，就是该城市只连接一个连通块，删除不影响其他连通块之间的通讯，也就是题目的普通警报

如果=0，那就是该城市是一个孤立的，没与其他城市连接，也是普通警报

eg:

比如有0 1 2 3 4 5六个城市，以及一些边

现在依次摧毁2 4 0城市

逆向看，先吧2 4 0全去掉，建立连通分量，假设有[1,3] [5]

恢复0，假设有边(0,2),(0,5)(0,3),那0 2不管，因为2摧毁了，

(0 5)合并，并记录5的代表元素 (0 3)合并，记录3的代表元素。发现与0有两个连通分量连接

合并之后就是[0,1,3,5]，于是可以看出摧毁0城市后[1,3]和[5]没法连通，所以红色警报

恢复4，现在的连通分量是[0,1,3,5],假设有边(4,1)(4,5),遍历邻居代表元素只有一个，说明4城市只连一个连通分量

摧毁它不影响。合并之后是[0,1,3,5,4]

恢复2，现在的连通分量是[0,1,3,5,4],假设2没有与这些城市的边，那只会为它建立一个单点连通分量

与它连接的连通分量个数为0，也是普通警报

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <set>

using namespace std;

vector<vector<int>> G;

unordered_map<int, int> father;
int findN(int a)
{
    if (a != father[a])
        father[a] = findN(father[a]);
    return father[a];
}
void unionSet(int a, int b)
{
    if (!father.count(a))
        father[a] = a;
    if (!father.count(b))
        father[b] = b;
    father[findN(a)] = findN(b);
}

int main()
{
    int m, n;
    cin >> m >> n;

    // 建图
    for (int i = 0; i < m; i++)
        G.push_back(vector<int>());
    int a, b;
    for (int i = 0; i < n; i++) //注意是无向图
    {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 读入摧毁的城市
    int k;
    cin >> k;
    vector<int> destory(k);
    unordered_set<int> flagdes; // 标记摧毁的城市，因为要判断邻居是不是正常城市
    for (int i = 0; i < k; i++)
    {
        cin >> destory[i];
        flagdes.insert(destory[i]);
    }

    // 建立 给出的k个城市全部摧毁时 的连通状态
    bool isover = 0;
    if (destory.size() == m)
        isover = 1;
    for (int i = 0; i < m; i++)
    {
        if (!flagdes.count(i))
        {
            father[i] = i;  //如果是孤立的一个点，单独建立一个集合
            // 遍历邻居，找未摧毁的城市union
            for (int j = 0; j < G[i].size(); j++)
            {
                if (!flagdes.count(G[i][j]))
                {
                    unionSet(i, G[i][j]);
                }
            }
        }
    }

    // 恢复destroy[i],判断摧毁它后是什么情况
    unordered_map<int, int> flag; // 0-普通警报 1-红色警报
    for (int i = k - 1; i >= 0; i--)
    {
        father[destory[i]] = destory[i];//恢复成单点连通分量
        unordered_set<int> liantong; // 看恢复的这个城市与几个连通块相连，如果大于1个，那摧毁时就是红色 否则是普通
        for (int j = 0; j < G[destory[i]].size(); j++)
        {
            if (!flagdes.count(G[destory[i]][j]))
            {
                liantong.insert(findN(G[destory[i]][j]));
                unionSet(destory[i], G[destory[i]][j]); // 恢复，加入到连通分量里
            }
        }
        if (liantong.size() > 1)
            flag[destory[i]] = 1;
        else
            flag[destory[i]] = 0;
        flagdes.erase(destory[i]); // 注意，恢复的城市去除标记
    }

    for (int i = 0; i < k; i++)
    {
        if (flag[destory[i]] == 0)
        {
            cout << "City " << destory[i] << " is lost." << endl;
        }
        else
        {
            cout << "Red Alert: City " << destory[i] << " is lost!" << endl;
        }
    }
    if (isover)
    {
        cout << "Game Over." << endl;
    }
}