分析
思路就是并查集求连通块,答案等于连通块的数量-1
段错误是因为M的范围大于1e5,我把数组开到1e6就能过
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+9;
int p[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b)
{
a=find(a),b=find(b);
if(a!=b) p[a]=b;
return ;
}
struct node
{
int u,v;
}e[N];
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=0; i<m; ++i)
{
int u,v;
scanf("%d %d",&u,&v);
e[i]={u,v};
}
while(k--)
{
int q;
scanf("%d",&q);
for(int i=1; i<=n; ++i) p[i]=i;
for(int i=0; i<m; ++i)
{
if(q!=e[i].u&&q!=e[i].v)
{
merge(e[i].u,e[i].v);
}
}
int cnt=0;
for(int i=1; i<=n; ++i)
{
if(i!=q&&i==p[i]) cnt++;
}
printf("%d\n",cnt-1);
}
return 0;
}