ABC292 D - Unicyclic Components

偏执的太偏执、 2024-03-24 15:12 9阅读 0赞

**ABC刷起来好爽，我要刷爆ABC！**

[D - Unicyclic Components (atcoder.jp)][D - Unicyclic Components _atcoder.jp]

题意：

![4b3b3c7d07934d6ba5b68afd5bb0130d.png][]

思路：

直接用并查集维护连通性就可以，暴力维护每一个连通块的点的数量和边的数量，判断是否相等即可

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long 
    const int mxn=2e5+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    
    map<int,int> cnt1,cnt2;
    int n,m,u,v;
    int f[mxn],U[mxn];
    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(){
        cnt1.clear(),cnt2.clear();
        cin>>n>>m;
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            U[i]=u;
            join(u,v);
        }
        for(int i=1;i<=n;i++){
            cnt1[find(i)]++;
        }
        for(int i=1;i<=m;i++){
            cnt2[find(U[i])]++;
        }
        if(cnt1==cnt2) cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

还有一个想法就是，就是一个连通块，n个点n条边，先连n-1条边变成一棵树，然后连最后一条边构成一整个连通块，那这个连通块只有一个环

然后只需要维护每个连通块的环的数量就可以了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    
    
    int n,m,u,v;
    int f[mxn],cnt[mxn];
    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;
        for(int i=1;i<=n;i++) f[i]=i,cnt[i]=0;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            if(find(u)==find(v)){
                cnt[find(u)]++;
                join(u,v);
            }else{
                join(u,v);
            }
        }
        for(int i=1;i<=n;i++){
            if(cnt[find(i)]!=1){
                cout<<"No"<<'\n';
                return;
            }
        }
        cout<<"Yes"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

然后 就wa了

![f7dc9db6a7b849d282b2376f365130af.jpeg][]

然后 jd一语中的

![f5e73aa5554148de8e6f078d4de0ac7b.png][]

一改就过了

真牛逼

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    
    
    int n,m,u,v;
    int f[mxn],cnt[mxn];
    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){
            if(cnt[f1]<1) f[f1]=f2;
            else f[f2]=f1;
        }
    }
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) f[i]=i,cnt[i]=0;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            if(find(u)==find(v)){
                cnt[find(u)]++;
                join(u,v);
            }else{
                join(u,v);
            }
        }
        for(int i=1;i<=n;i++){
            if(cnt[find(i)]!=1){
                cout<<"No"<<'\n';
                return;
            }
        }
        cout<<"Yes"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Unicyclic Components _atcoder.jp]: https://atcoder.jp/contests/abc292/tasks/abc292_d
[4b3b3c7d07934d6ba5b68afd5bb0130d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d0aa4f3a783447a3b30e7f98783ab347.png
[f7dc9db6a7b849d282b2376f365130af.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/828f80a5fbe24793800df2449bbd6d8a.png
[f5e73aa5554148de8e6f078d4de0ac7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6a38c30179fb4252afa26ef086f493cf.png