题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。

某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

输入输出格式

输入格式：

输入文件第一行包含两个整数，\(N (1 \leq N \leq 2M)\) 和 \(M(1 \leq M \leq 200,000)\)，分别表示星球的数目和以太隧道的数目。星球用 \(0\) ~ \(N-1\) 的整数编号。

接下来的 \(M\) 行，每行包括两个整数 \(X\), \(Y\)，其中\(（ 0 < = X <> Y\) 表示星球 \(X\) 和星球 \(Y\) 之间有 “以太” 隧道，可以直接通讯。

接下来的一行为一个整数 \(k\) ，表示将遭受攻击的星球的数目。

接下来的 \(k\) 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这 \(k\) 个数互不相同，且都在 \(0\) 到 \(n-1\) 的范围内。

输出格式：

第一行是开始时星球的连通块个数。接下来的 \(k\) 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

输入输出样例

输入样例#1：

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

输出样例#1：

1
1
1
2
3
3

说明

\([JSOI2008]\)

思路：这道题目的思路非常巧妙，我们用一个\(vis\)数组来记录一下被破坏的星球，然后用一个\(h\)数组来保存被破坏星球的顺序，然后按给出边的顺序合并并查集，求出k次破坏星球后还剩下的联通块个数，然后倒序枚举一个\(i\)，依次还原\(k\)个星球，然后继续求联通块个数，用一个\(a\)数组分别记录\(k\)次还原后的联通块个数，然后输出即可。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#define maxn 400007
using namespace std;
int n,m,k,a[maxn],fa[maxn],num,h[maxn],head[maxn];
bool vis[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int u,v,nxt;
}e[maxn];
inline void ct(int u, int v) {
  e[++num].u=u;
  e[num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void uni(int x, int y) {x=find(x),y=find(y);fa[y]=x;}
int main() {
  n=qread(),m=qread();
  for(int i=0;i<n;++i) fa[i]=i;
  for(int i=1,u,v;i<=m;++i) {
    u=qread(),v=qread();
    ct(u,v);ct(v,u);
  }
  scanf("%d",&k);
  int ltk=n-k;
  for(int i=1,x;i<=k;++i) {
    x=qread();
    vis[x]=1,h[i]=x;
  }
  for(int i=1;i<=(m<<1);++i) {
    int u=e[i].u,v=e[i].v;
    if(!vis[u]&&!vis[v]&&find(u)!=find(v)) uni(u,v),ltk--;
  }
  a[k+1]=ltk;
  for(int t=k;t>=1;--t) {
    int u=h[t];
    ltk++;
    vis[u]=0;
    for(int i=head[u];i;i=e[i].nxt) {
      int v=e[i].v;
      if(!vis[v]&&find(u)!=find(v)) uni(u,v),ltk--;
    }
    a[t]=ltk;
  }
  for(int i=1;i<=k+1;++i) printf("%d\n",a[i]);
  return 0;
}