团体程序设计天梯赛 决赛 L2 红色警报

题目链接：https://www.patest.cn/contests/gplt/L2-013

求联通块的个数，因为时限给的很宽，我们可以每一次都直接重新并查集建图处理，再来统计连通块的个数。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 505;
int set[maxn],n;
struct Road
{
  int u,v;
}r[maxn*10];
int cmp(Road a,Road b)
{
  return a.u < b.u;
}
int find(int x)
{
  int r = x;
  while(r != set[r])
    r = set[r];
  return r;
}
void merge(int a,int b)
{
  int x = find(a);
  int y = find(b);
  if(x != y) set[x] = y;
}
void init()
{
  for(int i=0; i<n; i++) set[i] = i;
}
int main()
{
  int m;
  scanf("%d%d", &n,&m);
  init();
  for(int i=0; i<m; i++)
  {
    scanf("%d%d", &r[i].u,&r[i].v);
    merge(r[i].u,r[i].v);
  }
  int sum = 0;
  for(int i=0; i<n; i++)
    if(set[i] == i) sum++;
  int q;
  scanf("%d", &q);
  for(int j=0; j<q; j++)
  {
    int tmp;
    scanf("%d", &tmp);
    init();
    int num = 0;
    for(int i=0; i<m; i++)
    {
      if(r[i].u == tmp || r[i].v == tmp) r[i].u = maxn-1,num++;
      else merge(r[i].u,r[i].v);
    }
    sort(r,r+m,cmp);
    m -= num;
    num = 0;
    for(int i=0; i<n; i++)
      if(set[i] == i) num++;
    if(num - sum > 1) printf("Red Alert: ");
    printf("City %d is lost",tmp);
    if(num - sum > 1) printf("!\n");
    else printf(".\n");
    sum = num;
    if(j == n-1) printf("Game Over.\n");
  }
}