【并查集】ABC229 E - Graph Destruction

「爱情、让人受尽委屈。」 2024-03-23 11:24 52阅读 0赞

[E - Graph Destruction (atcoder.jp)][E - Graph Destruction _atcoder.jp]

题意：

![0d7a9329af304dc2b9527c577df9a131.png][]

思路：

看了下面的图大概就知道做法了，倒着连接，然后并查集：

![5611b2979c1b4da089a7cc084d262e33.png][]

因为我们要维护的是连通块个数嘛，那么一定就是并查集维护连通块个数

而我们在用并查集维护连通块的时候，一般都是边加边边维护，所以我们考虑倒着维护

观察上图中倒着加边的**特殊性质**： 结点只和编号比它大的连边，因此每次加边只需要和编号比其大的连边即可

这样维护图的复杂度是O(n+m)

然后最后一件最重要的事情就是如何维护连通块个数

每新加一个结点，连通块个数cnt++

然后在连边之前如果该结点和u不属于一个连通块，那么cnt--

这样就能O(1)维护连通块个数了

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=1e18;
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    int n,m,u,v,tot=0;
    int head[mxn],f[mxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            f[i]=i;
        }
    }
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    void solve(){
        cin>>n>>m;
        G_init();
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        vector<int> v;
        int cnt=0;
        for(int u=n;u>=2;u--){
            cnt++;
            for(int i=head[u];~i;i=edge[i].next){
                if(edge[i].to<u) continue;
                if(find(u)!=find(edge[i].to)){
                    cnt--;
                }
                join(u,edge[i].to);
            }
            v.push_back(cnt);
        }
        reverse(v.begin(),v.end());
        v.push_back(0);
        for(int i=0;i<v.size();i++) cout<<v[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Graph Destruction _atcoder.jp]: https://atcoder.jp/contests/abc229/tasks/abc229_e
[0d7a9329af304dc2b9527c577df9a131.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/0fcab915b579480480b8de7c09580e4c.png
[5611b2979c1b4da089a7cc084d262e33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/36dd2942c483449fb3da30f22537601a.png