[数据结构与算法]7-24 红色警报 (25 分)---并查集

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
int p[510];
bool st[510];
int n,m;
vector<pair<int,int>>path;
int find(int x)
{
	if(p[x]!=x)return p[x]=find(p[x]);
	return p[x];
}
void init()
{
    for(int i=0;i<n;i++)p[i]=i;
}
void merge(int a,int b)
{
    int pa=find(a),pb=find(b);
    if(pa!=pb)p[pa]=pb;
}
signed main()
{
	cin>>n>>m;
	init();
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		merge(a,b);
		path.push_back({a,b});
	}
	int cnt=0,cnt1=0;
	for(int i=0;i<n;i++)if(p[i]==i)cnt++;
	int K;cin>>K;
	for(int u=0;u<K;u++)
	{
		int cnt1=0,x;cin>>x;
		init();
		st[x]=true;
		for(auto [a,b]:path)
		{
		    if(st[a]||st[b])continue;
		    merge(a,b);
		}
		for(int i=0;i<n;i++)if(p[i]==i&&!st[i])cnt1++;
		if(cnt1>cnt) cout<<"Red Alert: City "<<x<<" is lost!\n";
		else cout<<"City "<<x<<" is lost.\n";
		cnt=cnt1;
	}
	if(!cnt)cout<<"Game Over."<<endl;
}