L2-013 红色警报 分数 25 作者 陈越 单位 浙江大学
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
意思就是1个连通块，如果删掉x后就出现多个连通块了，那就是红色警报。如果删除x后，连通块个数不变，那是普通警报（不要发出警报，下面写成普通警报了，没办法了）
比如1 - 0 - 3 删除0 发出红色警报 1-0-3删除1发普通警报
输入格式：
输入在第一行给出两个整数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.#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;
}
}
标签：连通,星球大战,destory,int,城市,查集,father,建图,摧毁 From： https://www.cnblogs.com/fyjie/p/18035018