競プロノート

Appearance

Functional Graph ​

各頂点から出る有向辺がちょうど1本のグラフ。

特徴 ​

各頂点の遷移先を nxt[v] で管理できる。

cpp
vector<int> nxt(n);

例えば、次のようなグラフ。

text
0 → 1 → 2 → 3 → 4
    ↑   ↑       |
    5   └───────┘

このグラフでは 2 → 3 → 4 → 2 がサイクルになっている。

重要な性質 ​

  • 各頂点の出次数は必ず1。
  • 各弱連結成分には、有向サイクルがちょうど1つ存在する。
  • サイクル以外の頂点は、最終的にそのサイクルに到達する。
  • 自己ループも長さ1のサイクルとして扱う。
  • 頂点数Nなら、辺数もN。

つまり、各連結成分は 1つのサイクルと、そこに向かって伸びる木 から構成される。

典型的な解法 ​

やりたいこと解法
サイクルを見つける訪問状態を管理して辿る
サイクル上の頂点を列挙入次数0の頂点を削除
K回遷移した先を求めるダブリング
サイクルまでの距離トポロジカルな削除順を逆に処理
強連結成分に分解するSCC

サイクル上の頂点を求める ​

入次数0の頂点を順番に削除すると、最後にサイクル上の頂点だけが残る。

cpp
vector<int> indeg(n);
for (int v = 0; v < n; v++) indeg[nxt[v]]++;

queue<int> q;
for (int v = 0; v < n; v++) {
    if (indeg[v] == 0) q.push(v);
}

while (!q.empty()) {
    int v = q.front(); q.pop();
    int nv = nxt[v];
    if (--indeg[nv] == 0) q.push(nv);
}

// indeg[v] > 0 ならサイクル上の頂点

計算量：O(N)

K回遷移した先を求める ​

nxt[v] を繰り返し適用する。

Kが大きい場合は、ダブリングで高速化できる。

  • 前処理：O(N log K)
  • クエリ：O(log K)

注意点 ​

  • 一般の有向グラフと異なり、各頂点の出次数はちょうど1。
  • 各弱連結成分にサイクルは必ず1つ存在する。
  • 自己ループもサイクルに含まれる。
  • 非連結な場合、サイクルは複数存在することがある。
  • サイクル上の頂点以外は、削除順を逆に処理すると距離などをDPできる。

関連 ​

  • SCC
  • DFS
  • ダブリング
  • トポロジカルソート