本質

次に見る頂点が 訪れたことはあるけど再帰呼び出し前の頂点ではなかったら その見ている頂点と今いる頂点は閉路で結ばれている.

引用 https://drken1215.hatenablog.com/entry/2023/05/20/200517

実際の実装でやることはbool配列 seenとfinishedを持ち行きがけにseenを,帰りがけにfinishedをtrueにする.

次に見る頂点が seen[next] && !finished[next] == true ならば閉路がある.

閉路復元はstackを用いればよい.

行きがけにstackにpush,帰りがけにpopし閉路を見つけたら何も考えずにstackを辿ればよい.

例題 ABC 311 C

https://atcoder.jp/contests/abc311/tasks/abc311_c

本質部分のコード

    vector<bool> seen(n),finished(n);
    stack<int> hist;
    vector<int> ans;
    auto dfs = [&] (auto dfs,int v) -> void {
        seen[v] = true;
        hist.push(v);
        for(auto next:g[v]){
            if(seen[next] && !finished[next]) {
                while(!hist.empty()){
                    int h = hist.top();
                    ans.emplace_back(h+1);
                    hist.pop();
                    if(h==next) break;
                }
            }
            if(seen[next]) continue;
            dfs(dfs,next);
        }
        finished[v] = true;
    };

https://atcoder.jp/contests/abc311/submissions/52702940

一応(この問題はfunctional graphなのでwhile回すだけでACはできる.)