篮球杯【并查集】发现环

谁践踏了优雅 2024-03-25 10:14 40阅读 0赞

[发现环 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

题意:

![aa1bcadefde095cbab2818e729c3fa3d.png][]

思路：

判环可以用并查集，也可以用拓扑排序

这里用并查集，就是一条一条加边，直到在加u和v之前发现find(u)==find(v)的时候就确定有环了

确定有环之后，我们可以从u DFS输出环

怎么DFS，只需写个带回溯的DFS就行了，如果没有碰到环就回溯，碰到了就输出答案

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    
    
    vector<int> ans;
    int n,m,u,v,st,ed,tot=0;
    int f[mxn],vis[mxn],head[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 print(){
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++) cout<<ans[i]<<" \n"[i==ans.size()-1];
    }
    void dfs(int u,int dep){
        if(u==ed){
            print();
            return;
        }
        for(int i=head[u];~i;i=edge[i].next){
            if(!vis[edge[i].to]){
                vis[edge[i].to]=1;
                ans.push_back(edge[i].to);
                dfs(edge[i].to,dep+1);
                vis[edge[i].to]=0;
                ans.pop_back();
            }
        }
    }
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void solve(){
        cin>>n;
        init();
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=n;i++){
            cin>>u>>v;
            if(find(u)==find(v)){
                st=u,ed=v;
                vis[st]=1;
                ans.push_back(st);
                dfs(st,1);
                return;
            }else join(u,v);
            add(u,v);
            add(v,u);
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/108/learning/?page=1&first_category_id=1&sort=students_count&difficulty=30&second_category_id=3&name=%E5%8F%91%E7%8E%B0%E7%8E%AF
[aa1bcadefde095cbab2818e729c3fa3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7423f169a3454249ac69d5251903864c.png