题目描述
很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。
某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。
但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，
两个星球之间的通讯通道也开始不可靠起来。
现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。
（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。
输入格式
输入文件第一行包含两个整数，NN (1 < = N < = 2M1<=N<=2M) 和 MM (1 < = M < = 200,0001<=M<=200,000)，分别表示星球的数目和以太隧道的数目。星球用 00 ~ N-1N−1 的整数编号。
接下来的 MM 行，每行包括两个整数 XX, YY，其中（ 0 < = X <> Y0<=X<>Y 表示星球 xx 和星球 yy 之间有 “以太” 隧道，可以直接通讯。
接下来的一行为一个整数 kk ，表示将遭受攻击的星球的数目。
接下来的 kk 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这 kk 个数互不相同，且都在 00 到 n-1n−1 的范围内。
输出格式
第一行是开始时星球的连通块个数。接下来的 KK 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。
题解：并查集可以支持合并，查询操作，好像并不能支持删除操作，所以对于这道题我们要离线做，先默认所有点各自就是一个连通块，先把所有摧毁的点以及离连边去掉，
算出此时联通块的个数即为最后一次轰炸结束后的联通块个数，然后根据轰炸操作依次从后往前加点和邻边，每加一个点计算并记录一下联通块的个数，最后正序输出即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 200005 6 7 using namespace std; 8 9 struct node 10 { 11 int st,ed,nxt; 12 }; 13 node edge[maxn<<1]; 14 int n,m,k,ans[maxn<<1],h[maxn<<1],f[maxn<<1],first[maxn<<1],cnt; 15 //int st[maxn],ed[maxn]; 16 bool bum[maxn<<1]; 17 18 inline void add_edge(int s,int e) 19 { 20 cnt++; 21 edge[cnt].st=s; 22 edge[cnt].ed=e; 23 edge[cnt].nxt=first[s]; 24 first[s]=cnt; 25 return; 26 } 27 28 inline int find(int b) 29 { 30 if(f[b]==b) return f[b]; 31 return f[b]=find(f[b]); 32 } 33 34 35 int main() 36 { 37 scanf("%d%d",&n,&m); 38 for(int i=1;i<=m;i++) 39 { 40 int s,e; 41 scanf("%d%d",&s,&e); 42 add_edge(s+1,e+1); add_edge(e+1,s+1); 43 //st[i]=s+1; ed[i]=e+1; 44 } 45 scanf("%d",&k); 46 int num=n; 47 for(int i=1;i<=k;i++) 48 { 49 scanf("%d",&h[i]); 50 h[i]++; 51 bum[h[i]]=true; 52 num--; 53 } 54 for(int i=1;i<=n;i++) f[i]=i; 55 for(int i=1;i<=2*m;i++) 56 { 57 if(bum[edge[i].st]==false&&bum[edge[i].ed]==false) 58 { 59 int f1=find(edge[i].st),f2=find(edge[i].ed); 60 if(f1!=f2) 61 { 62 num--; 63 f[f1]=f2; 64 } 65 } 66 } 67 ans[k+1]=num; 68 for(int i=k;i>=1;i--) 69 { 70 bum[h[i]]=false; 71 num++; 72 for(int j=first[h[i]];j!=0;j=edge[j].nxt) 73 { 74 int e=edge[j].ed; 75 if(!bum[e]) 76 { 77 int f1=find(h[i]); 78 int f2=find(e); 79 if(f1!=f2) 80 { 81 f[f1]=f2; 82 num--; 83 } 84 } 85 } 86 ans[i]=num; 87 } 88 for(int i=1;i<=k+1;i++) 89 printf("%d ",ans[i]); 90 return 0; 91 }