関数グラフのcycle・tree分解
概要
各頂点の後続が一意なgraphをcycleと流入treeへ分解し、前周期・周期を処理する。
考え方
各頂点から出る辺がちょうど一本なら、どの頂点から進んでも、有限個の頂点のどれかを再訪する。再訪後は同じ道を繰り返すので、移動は「サイクルへ入るまで」と「サイクル上」に分けられる。サイクルへ流れ込む部分は、辺がサイクルの方を向いた木になる。
以下は公式の入力例とは別の、独自の小例である。頂点を とし、後続を表す写像を 、つまり とする。
中央の がサイクルで、 と がそこへ流れ込む木の辺である。出発点にいる時点を時刻0とする。頂点1から進むと、 歩後の頂点は順に となる。
入次数0を剥がすと何が残るか
全頂点の入次数を数え、入次数0の頂点をキューへ入れる。頂点 を除くたびに後続 の入次数を1減らし、0になったらキューへ追加する。除去した順序を配列 order に保存する。小例では頂点1と4を除くと、頂点2と3だけが残る。サイクル上の頂点は、直前の頂点からの辺があるため除去されない。
一般の有向グラフでは、この処理でサイクル以外も残る。例えば に辺 を足すと、どの頂点も入次数0にならず、サイクル外の頂点3も残る。
出次数1の場合は、残る頂点から除去済みの頂点へ向かう辺がない。そのような辺があれば、除去時の入次数が0だったことに矛盾する。従って、残存頂点数を とすると、残存辺数も 本である。一方、処理終了時の各頂点の入次数は1以上で、その総和は辺数と等しい だから、入次数はすべて1になる。出次数も1なので、残るグラフは互いに交わらないサイクルだけである。
サイクルの入口と距離を分けて持つ
未採番の残存頂点から後続をたどって一周し、サイクルの頂点を進行順に配列へ並べる。各頂点にサイクルID、周上の位置、サイクルまでの距離0を付ける。以後、cycle[id] をその配列、cycleId[v] を頂点 が到達するサイクルのIDとする。
さらに、dist[v] をサイクルへ初めて着くまでの歩数、entryPos[v] をその入口の配列内位置とする。サイクル上の頂点では、入口は自分自身である。小例で配列を cycle[0] = [2, 3] とすると、属性は次のようになる。
| 頂点 | cycleId | dist | entryPos |
|---|---|---|---|
| 1 | 0 | 1 | 0 |
| 2 | 0 | 0 | 0 |
| 3 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 |
頂点1と2は同じ入口を持つが、そこまでの距離は異なる。頂点1と4は距離が同じでも、入口の位置は異なる。この二つの属性を分けることで、木の部分と周上の移動を接続できる。
木の属性は order を逆順に読んで埋める。除去した頂点の後続は、サイクル上に残るか、その頂点より後に除去されるので、逆順では後続の属性が既に分かっている。そこで、 のサイクルIDと入口の位置を からコピーし、距離を
とする。
歩数から木の部分を引いて周期へつなぐ
から 歩進むとき、 なら、最初の 歩は入口へ着くために使う。サイクル上で進むのは残りの 歩なので、サイクル長を として答えの位置は
になる。cycle[cycleId[v]] のこの位置にある頂点を返す。頂点1から3歩なら、入口へ1歩、周上で2歩なので、位置は 、答えは頂点2である。距離を引かないと、木で使った一歩まで周上の移動として数えてしまう。
では、まだ木の途中なのでサイクルの式は使えない。小例の頂点1から0歩の答えは頂点1であり、サイクル配列には含まれない。この場合は doubling・binary lifting で 回後を求める。 ではちょうど入口、 ではそこから一周して同じ入口となる。
成立条件と計算量
対象は 頂点で各頂点の後続が一意に決まる関数グラフである。各頂点を高々一回除去し、各サイクルを一周し、除去順を一回逆に読むので、分解と属性の構築は 時間・空間で済む。サイクル到着後の行き先は、属性と配列から一回の質問につき 時間で求まる。
木の途中への質問も扱うなら、索引の追加費用を分解と分けて数える。上の方法では木の移動は に限るため、ダブリング表は最大 歩を扱えればよい。この表の構築・空間は 、木部分の質問は 時間となる。巨大な のサイクル部分は剰余で処理するため、この索引を の桁数まで増やす必要はない。
自己ループは長さ1のサイクルとして扱える。複数成分があればそれぞれを採番し、木の経路が合流するときも後続の属性を各頂点へ伝播すればよい。、サイクル直前、入口到着、一周後を区別して確認する。
行き先に加えて途中の累積値も必要なら、次のダブリング単元で同じ写像に出発点の寄与を載せ、移動と集約を一緒に合成する。
問題一覧
- ABC436 E「Minimum Swap」 公式問題
- ABC296 E「Transition Game」 公式問題
- ABC256 E「Takahashi's Anguish」 公式問題
- ABC241 E「Putting Candies」 公式問題
- ABC357 E「Reachability in Functional Graph」 公式問題
- ABC377 E「Permute K times 2」 公式問題組合せ: 法上の四則演算・高速累乗・逆元
技能・出典
主題: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 関数グラフのcycle・tree分解 / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC387 F「Count Arrays」 公式問題
技能・出典
主題: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。 cycle縮約後の木でdp[v][j]=∏_{子u}Σ_{k≤j}dp[u][k]。子ごとにprefix和を作れば、親の値ごとに子の全値を走査する二乗因子が消える。functional graph縮約と木DPを先に履修する。主タグ: 関数グラフのcycle・tree分解 / 補助タグ: DP遷移の集約・高速化、根付き木DP・部分木集約
- ABC399 E「Replace」 公式問題
- ABC284 G「Only Once」 公式問題
技能・出典
主題: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: 関数グラフのcycle・tree分解 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、状態・配置の正規化
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC258 E「Packing Potatoes」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 尺取り法・sliding window / 補助タグ: 関数グラフのcycle・tree分解
- ABC371 G「Lexicographically Smallest Permutation」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。追加で学ぶ技能: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 貪欲法と交換論、一次合同・CRT / 補助タグ: 関数グラフのcycle・tree分解
- ABC444 G「Kyoen」 公式問題主題: Gaussian整数・二平方和
技能・出典
主題: Gaussian整数・二平方和(Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: Gaussian整数・二平方和 / 補助タグ: 関数グラフのcycle・tree分解
前提・学習成果・出典
習得対象の目安: 水色(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頂点の小例と入次数による分解の論証は、本書の独自の説明である。