2022天梯赛三月冲刺——PAT (Advanced Level)1013 Battle Over Cities (并查集找连通块)

#include <cstdio>
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>V[1005];
int fa[1005];
int n,m,k;
void init()
{
  for(int i = 1;i <= n;i++)
  {
    fa[i]=i;
  }
}
int findf(int x)
{
  if(x==fa[x]) return x;
  return fa[x]=findf(fa[x]);
}
int main()
{
  cin >> n >> m >> k;
  for(int i = 1;i <= m;i++)
  {
    int a,b;
    cin >> a >> b;
    V[a].push_back(b);
    V[b].push_back(a);
  }
  for(int i = 1;i <= k;i++)
  {
    init();
    int tt;
    cin >> tt;
    for(int j = 1;j <= n;j++)
    {
      if(j==tt) continue;
      for(int z = 0;z < V[j].size();z++)
      {
        if(V[j][z]==tt) continue;
        int a=findf(j);
        int b=findf(V[j][z]);
        if(a!=b) fa[a]=b;
      }
    }
    int ans=0;
    for(int ii = 1;ii <= n;ii++)
    {
      if(findf(ii)==ii) ans++;
    }
    if(i!=k) cout << ans-2 <<endl;
    else cout << ans-2;
  }
  return 0 ;
}