AcWing 1485. 战争中的城市
原题链接
中等
作者:
12..
,
2021-07-17 17:09:50
,
所有人可见
,
阅读 309
#include<iostream>
using namespace std;
const int N=1010;
const int M=(N-1)*N/2;
int f[N];
struct edge
{
int a,b;
}e[M];
int find(int x){
if(x!=f[x]){
f[x]=find(f[x]);
}
return f[x];
}
void merge(int a,int b)
{
f[a]=b;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<m;i++){//需要将便存储起来
cin>>e[i].a>>e[i].b;
}
for(int i=0;i<k;i++){
int x;cin>>x;
int cnt=n;//初始时有n个连通块
//初始化并查集
for(int j=1;j<=n;j++){
f[j]=j;
}
for(int j=0;j<m;j++){
int u=e[j].a,v=e[j].b;
if(u!=x&&v!=x){
//加入与x无关的边
u=find(u);v=find(v);
if(u!=v){
merge(u,v);
cnt--;//每个并一个连通块,连通块个数减1
}
}
}
cout<<cnt-2<<endl;
}
return 0;
}