AcWing 1485. 战争中的城市
原题链接
中等
作者:
在月球_0
,
2024-11-06 09:10:55
,
所有人可见
,
阅读 1
#include <iostream>
using namespace std;
const int N = 1010,M = 500010;
int n,m,k;
int p[N];
struct edge{
int a,b;
}e[M];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i = 0;i < m;i++) scanf("%d%d",&e[i].a, &e[i].b);
while(k--)
{
//重点关注的城市数量
int x;
scanf("%d",&x);
int cnt = n - 1;
//并查集操作
//注意:编号为1到N
for(int i = 1;i <= n;i++) p[i] = i;
for(int i = 0;i < m;i++)
{
int a = e[i].a,b = e[i].b;
if(a != x && b != x)
{
//合并
int pa =find(a),pb = find(b);
if(pa != pb)
{
p[pa] = pb;
cnt--;
}
}
}
printf("%d\n",cnt - 1);
}
return 0;
}