P1197 星球大战

题目链接：点击打开链接

题目描述

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

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

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

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

输入文件第一行包含两个整数， 

$N$ ( $1<=N<=2M$ ) 和 $M$ ( $1<=M<=200,000$ )，分别表示星球的数目和以太隧道的数目。星球用 $0$ ~ $N?1$ 的整数编号。

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

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

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

输出格式：

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

输入：

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
2
3
3

思路：并查集，+逆序做

将摧毁，变成收复，从后往前检查

code：

#include<iostream>
using namespace std;
const int maxn=400002;
struct point
{int from;int to;int next;
}a[maxn];
int f[maxn];   //并查集
int last[maxn];//链表
int h[maxn];//破环的星球
int ans[maxn];//每次打击后的结果
bool e[maxn];//判断是否被打击
int tot;
int Find(int x)
{if(f[x]!=x)f[x]=Find(f[x]);return f[x];
}
inline void add(int x,int y)//邻链表储存数据
{a[tot].next=last[x];a[tot].from=x;a[tot].to=y;last[x]=tot;++tot;
}
int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;++i){f[i]=i;last[i]=-1;}int x,y;for(int i=1;i<=m;++i){cin>>x>>y;add(x,y);add(y,x);//双向，后面 tot=2*m}int k;cin>>k;int cnt=n-k;//表示破坏完之后还有多少个星球for(int i=1;i<=k;++i){cin>>x;e[x]=true;//表示破坏了h[i]=x;}for(int i=0;i<tot;++i){if(!e[a[i].from]&&!e[a[i].to])//没有被打击{if(Find(a[i].from)!=Find(a[i].to))//没有来联通{--cnt;f[Find(a[i].from)]=Find(a[i].to);//合并，加一}}}ans[k+1]=cnt;//记录全部被破坏之后的联通块for(int i=k;i>=1;--i)//从后往前”恢复“{x=h[i];++cnt;e[x]=false;//修复，加一for(int j=last[x];j!=-1;j=a[j].next)//邻链表遍历所有{if(!e[a[j].to]&&f[Find(x)]!=Find(a[j].to))//恢复之后没有被打击，并不相连{cnt--;f[Find(a[j].to)]=Find(x);//合并，加一}}ans[i]=cnt;//记录当前的联通块}for(int i=1;i<=k;++i)cout<<ans[i]<<endl;cout<<ans[k+1];return 0;
}