并查集维护集合

---

这道题code写起来很容易

但有很多启示

这道题需要逆序做

为什么呢？

对于路径压缩的并查集来说，如果合并了。那么想要在分开是很难的。

而且这道题要求每步输出。但是！！ 这道题是先给操作，再统一输出！！ 我们就可以离线做

那么我们就可以逆序做

先处理最后的状态，然后倒着合并。这样的话，就可以很快的跑出来了

对于合并容易，分开难得数据结构。在要求支持分开的离线操作题中。我们可以将分开换做合并。 倒着做

#include
    
     #include
     
      #include
      
       using namespace std;int f[401000];int find(int x){    if(f[x]==x)        return x;    return f[x]=find(f[x]);}struct node{    int point;    int nxt;};node l[401000];int head[401000],tail;int in[401000][2];void add(int x,int y){    l[++tail].point=y;    l[tail].nxt=head[x];    head[x]=tail;}int able[400010];bool use[400010];int ans[400010];int main(){    int n,m,k;    scanf("%d%d",&n,&m);    for(int i=0;i
       
        =1;i--)    {        ans[i]=tot;        for(int need=head[able[i]];need;need=l[need].nxt)        {            int f1=find(able[i]),f2=find(l[need].point);            if(f1!=f2&&!use[l[need].point])            {                tot-=1;                f[f1]=f2;            }        }        tot+=1;//因为第一次合并时，集合数并不会减少，所以这里将tot补回来        use[able[i]]=false;    }    ans[0]=tot;    for(int i=0;i<=k;i++)        printf("%d\n",ans[i]);}/*5 70 10 20 42 32 11 33 13241*/