题目描述:
并查集基础题,具体思路备注在代码内,代码如下:
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 505;
const int MAX_M = 5005;
int pre[MAX_N]; //每个城市的“上级”
int vis[MAX_N]; //标记是否被攻占
struct Road
{
int x, y; //道路连接的两个城市
}road[MAX_M];
void init(int n)
{
for (int i = 0; i < n; i++)
pre[i] = i;
}
int find_pre(int key)
{
if (pre[key] == key)
return key;
return pre[key] = find_pre(pre[key]);
}
void unite(int x, int y)
{
int rootx = find_pre(x);
int rooty = find_pre(y);
if (rootx != rooty)
pre[rootx] = rooty;
}
int main()
{
int n, m, k;
cin >> n >> m;
init(n);
for (int i = 0; i < m; i++)
{
cin >> road[i].x >> road[i].y;
unite(road[i].x, road[i].y);
}
int oldCity = 0;
for (int i = 0; i < n; i++) //算出最初的城市的数量
{
if (pre[i] == i)
oldCity++;
}
cin >> k;
int count = 0; //记录被攻占的城市数
for (int i = 0; i < k; i++)
{
int lost; //被攻占的城市编号
cin >> lost;
vis[lost] = 1; //标记已被攻占
count++;
init(n); //初始化城市的连接状态
for (int j = 0; j < m; j++)
{
//如果该道路连接的两个城市都未被攻占,则连接起来
if (vis[road[j].x] == 0 && vis[road[j].y] == 0)
unite(road[j].x, road[j].y);
}
//计算被攻占一座城市后的连通情况
int newCity = 0;
for (int i = 0; i < n; i++)
{
if (pre[i] == i)
newCity++;
}
//如果被攻占的是原本就独立的城市或者单独这个城市被攻占而不影响其余城市的连通情况
if (newCity == oldCity || newCity == oldCity + 1)
printf("City %d is lost.\n", lost);
//否则就代表连通度改变
else
printf("Red Alert: City %d is lost!\n", lost);
//如果全部城市被攻占
if (count == n)
printf("Game Over.");
oldCity = newCity; //更新为上次被攻占完后的连通情况
}
return 0;
}