関数グラフのcycle・tree分解

概要

各頂点の後続が一意なgraphをcycleと流入treeへ分解し、前周期・周期を処理する。

考え方

各頂点から出る辺がちょうど一本なら、どの頂点から進んでも、有限個の頂点のどれかを再訪する。再訪後は同じ道を繰り返すので、移動は「サイクルへ入るまで」と「サイクル上」に分けられる。サイクルへ流れ込む部分は、辺がサイクルの方を向いた木になる。

以下は公式の入力例とは別の、独自の小例である。頂点を 1,2,3,41,2,3,4 とし、後続を表す写像を f=(2,3,2,3)f=(2,3,2,3)、つまり f(1)=2,f(2)=3,f(3)=2,f(4)=3f(1)=2,f(2)=3,f(3)=2,f(4)=3 とする。

1⟶2⇄3⟵41\longrightarrow 2\rightleftarrows 3\longleftarrow 4

中央の 2→3→22\to3\to2 がサイクルで、1→21\to2 と 4→34\to3 がそこへ流れ込む木の辺である。出発点にいる時点を時刻0とする。頂点1から進むと、K=0,1,2,3K=0,1,2,3 歩後の頂点は順に 1,2,3,21,2,3,2 となる。

入次数0を剥がすと何が残るか

全頂点の入次数を数え、入次数0の頂点をキューへ入れる。頂点 vv を除くたびに後続 f(v)f(v) の入次数を1減らし、0になったらキューへ追加する。除去した順序を配列 order に保存する。小例では頂点1と4を除くと、頂点2と3だけが残る。サイクル上の頂点は、直前の頂点からの辺があるため除去されない。

一般の有向グラフでは、この処理でサイクル以外も残る。例えば 1→2→11\to2\to1 に辺 2→32\to3 を足すと、どの頂点も入次数0にならず、サイクル外の頂点3も残る。

出次数1の場合は、残る頂点から除去済みの頂点へ向かう辺がない。そのような辺があれば、除去時の入次数が0だったことに矛盾する。従って、残存頂点数を RR とすると、残存辺数も RR 本である。一方、処理終了時の各頂点の入次数は1以上で、その総和は辺数と等しい RR だから、入次数はすべて1になる。出次数も1なので、残るグラフは互いに交わらないサイクルだけである。

サイクルの入口と距離を分けて持つ

未採番の残存頂点から後続をたどって一周し、サイクルの頂点を進行順に配列へ並べる。各頂点にサイクルID、周上の位置、サイクルまでの距離0を付ける。以後、cycle[id] をその配列、cycleId[v] を頂点 vv が到達するサイクルのIDとする。

さらに、dist[v] をサイクルへ初めて着くまでの歩数、entryPos[v] をその入口の配列内位置とする。サイクル上の頂点では、入口は自分自身である。小例で配列を cycle[0] = [2, 3] とすると、属性は次のようになる。

頂点cycleIddistentryPos
1010
2000
3001
4011

頂点1と2は同じ入口を持つが、そこまでの距離は異なる。頂点1と4は距離が同じでも、入口の位置は異なる。この二つの属性を分けることで、木の部分と周上の移動を接続できる。

木の属性は order を逆順に読んで埋める。除去した頂点の後続は、サイクル上に残るか、その頂点より後に除去されるので、逆順では後続の属性が既に分かっている。そこで、vv のサイクルIDと入口の位置を f(v)f(v) からコピーし、距離を

dist[v]=dist[f(v)]+1\mathrm{dist}[v]=\mathrm{dist}[f(v)]+1

とする。

歩数から木の部分を引いて周期へつなぐ

vv から KK 歩進むとき、K≥dist[v]K\geq\mathrm{dist}[v] なら、最初の dist[v]\mathrm{dist}[v] 歩は入口へ着くために使う。サイクル上で進むのは残りの K−dist[v]K-\mathrm{dist}[v] 歩なので、サイクル長を CC として答えの位置は

(entryPos[v]+K−dist[v]) mod C\bigl(\mathrm{entryPos}[v]+K-\mathrm{dist}[v]\bigr)\bmod C

になる。cycle[cycleId[v]] のこの位置にある頂点を返す。頂点1から3歩なら、入口へ1歩、周上で2歩なので、位置は (0+3−1) mod 2=0(0+3-1)\bmod2=0、答えは頂点2である。距離を引かないと、木で使った一歩まで周上の移動として数えてしまう。

K<dist[v]K<\mathrm{dist}[v] では、まだ木の途中なのでサイクルの式は使えない。小例の頂点1から0歩の答えは頂点1であり、サイクル配列には含まれない。この場合は doubling・binary lifting で KK 回後を求める。K=dist[v]K=\mathrm{dist}[v] ではちょうど入口、K=dist[v]+CK=\mathrm{dist}[v]+C ではそこから一周して同じ入口となる。

成立条件と計算量

対象は N≥1N\geq1 頂点で各頂点の後続が一意に決まる関数グラフである。各頂点を高々一回除去し、各サイクルを一周し、除去順を一回逆に読むので、分解と属性の構築は O(N)O(N) 時間・空間で済む。サイクル到着後の行き先は、属性と配列から一回の質問につき O(1)O(1) 時間で求まる。

木の途中への質問も扱うなら、索引の追加費用を分解と分けて数える。上の方法では木の移動は K<dist[v]≤N−1K<\mathrm{dist}[v]\leq N-1 に限るため、ダブリング表は最大 N−1N-1 歩を扱えればよい。この表の構築・空間は O(Nlog⁡(N+1))O(N\log(N+1))、木部分の質問は O(log⁡(N+1))O(\log(N+1)) 時間となる。巨大な KK のサイクル部分は剰余で処理するため、この索引を KK の桁数まで増やす必要はない。

自己ループは長さ1のサイクルとして扱える。複数成分があればそれぞれを採番し、木の経路が合流するときも後続の属性を各頂点へ伝播すればよい。K=0K=0、サイクル直前、入口到着、一周後を区別して確認する。

行き先に加えて途中の累積値も必要なら、次のダブリング単元で同じ写像に出発点の寄与を載せ、移動と集約を一緒に合成する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。前周期と周期を分離し、cycleへの流入と巨大回数の移動を扱う。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 一意な後続・サイクル・ダブリング。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-functional-graph-decomposition

関数グラフのcycle・tree分解

習得する技能

  • 後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 状態グラフのモデリングと探索。

このUnitを直接前提とする単元: なし。

状態グラフのモデリングと探索で得た考え方と実装を再利用し、関数グラフのcycle・tree分解の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 関数グラフのcycle・tree分解の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠

2026-10-28にABC241 Eの公式問題文・個別公式解説を再照合した。同問では、アメの個数の剰余を状態、操作前の剰余で選ぶ追加個数を出発点の寄与とする。公式解説は周期を使う方法とダブリングの両方を示している。本文の4頂点の小例と入次数による分解の論証は、本書の独自の説明である。