AtCoder ABC 311 C - Find it! (茶色, 350 点)

Functional グラフのサイクル検出問題！

• 問題へのリンク

問題概要

頂点数 のグラフが与えられる。頂点 からは頂点 への辺が接続していて、辺数は全部で 本ある。

このグラフにおいて、同一頂点を複数回含まない有向サイクルをひとつ求めてください。具体的には、サイクルに含まれる頂点数と、サイクルをなす頂点を順に出力してください。

(入力例 1 の図)

制約

• 

考えたこと

この問題について語るべきことは、次の記事で語り尽くしました！！

drken1215.hatenablog.com

Functional グラフは、各頂点 に対して、その頂点を始点とする有向辺が 1 本だけ出ているような有向グラフです。下図のように、各連結成分ごとにちょうど 1 個ずつ閉路があります (このことの厳密な証明はここにあります)。

このことを、直感的に理解してみましょう。下図のように、Functional グラフ上のある頂点 を好きに選びます。この頂点 から出発して、行き先の頂点への移動を繰り返していくことを考えます。

このとき、この移動が無限に続くなどということはあり得ません。したがって、いつかは過去に訪れたことのある頂点に再度戻って来ます。そこから先は、サイクル上でループすることになります。

注意点としては、始点である頂点 がサイクル上にあるとは限らないことに注意しましょう。

そこで、頂点 に対して「辺を辿る」という移動をあらかじめ 回やっておくことにします。 回移動した後の頂点 は、サイクル内部にいるはずです (十分な回数の移動をしたため)。

その頂点 から出発して、再び頂点 に戻ってくるまで、有向辺を辿りましょう。こうして有向サイクルを検出できます。

計算量は です。

コード

#include <bits/stdc++.h>
using namespace std;

// G[v] := 頂点 v の行き先の頂点
vector<int> detect_cycle(const vector<int> &G) {
    // 頂点を 1 つ好きに選んで、N 回移動する
    int v = 0;
    for (int i = 0; i < (int)G.size(); ++i) v = G[v];
    
    // 得られた頂点から出発してサイクルを検出する
    vector<int> res;
    int s = v;
    do {
        res.push_back(v);
        v = G[v];
    } while (v != s);
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) { cin >> A[i]; --A[i]; }
    
    // 閉路検出
    const auto &res = detect_cycle(A);
    cout << res.size() << endl;
    for (auto v : res) cout << v+1 << " ";
    cout << endl;
}