Graph/CycleDetection.hpp

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Graph/CycleDetection.hpp"

Verified with

• test/yosupo_CycleDetection.test.cpp

Code

vector<int> CycleDetection(vector<vector<int>> &g){
    int n=(int)g.size();
    vector<int> check(n,0),cyc,pre(n,-1);

    function<bool(int)> dfs=[&](int cur){
        check[cur]=1;
        for(auto &to:g[cur]){
            if(check[to]==0){
                pre[to]=cur;
                if(dfs(to)) return true;
            }else if(check[to]==1){// detect
                int v=cur;
                while(v!=to){
                    cyc.push_back(v);
                    v=pre[v];
                }
                cyc.push_back(v);
                return true;
            }
        }
        check[cur]=2;
        return false;
    };

    rep(i,n){
        if(check[i]==0){
            if(dfs(i)){
                reverse(begin(cyc),end(cyc));
                return cyc;
            }
        }
    }
    return {};
}

#line 1 "Graph/CycleDetection.hpp"
vector<int> CycleDetection(vector<vector<int>> &g){
    int n=(int)g.size();
    vector<int> check(n,0),cyc,pre(n,-1);

    function<bool(int)> dfs=[&](int cur){
        check[cur]=1;
        for(auto &to:g[cur]){
            if(check[to]==0){
                pre[to]=cur;
                if(dfs(to)) return true;
            }else if(check[to]==1){// detect
                int v=cur;
                while(v!=to){
                    cyc.push_back(v);
                    v=pre[v];
                }
                cyc.push_back(v);
                return true;
            }
        }
        check[cur]=2;
        return false;
    };

    rep(i,n){
        if(check[i]==0){
            if(dfs(i)){
                reverse(begin(cyc),end(cyc));
                return cyc;
            }
        }
    }
    return {};
}

Back to top page