連結成分を管理し縮約する
概要
無向グラフで辺を何本かたどって行き来できる頂点を、ひとまとまりの連結成分として扱う。同じ成分に属するかだけで答えが決まるなら、質問のたびに経路を探す代わりに、成分の番号や代表を調べればよい。さらに、頂点数や黒い頂点の個数を成分ごとに持つと、成分全体についての質問にも答えられる。
この単元では、必要な答えと更新の種類から、静的な探索、辺追加に対する成分併合、頂点間の差の保持を選び分ける。
考え方
四頂点に無向辺1–2、2–3、1–3を順に追加する独自例を考える。初めは各頂点が別成分で、成分数は4。最初の二辺で成分数は3、2と減り、最後の辺では変わらない。1と3は既に2を経由してつながっているからである。最後は三頂点の成分と孤立頂点4の二成分になる。
ここで、何をいつ知りたいかによって手法を選ぶ。
- 全辺が決まった後に成分を知りたい。 未訪問の頂点からDFS・BFSを行い、到達した頂点へ同じ成分番号を付ける。この例なら1から1・2・3を訪問し、残る4から別の探索を始める。
- 辺を追加するたびに連結性を知りたい。 成分は併合されるだけで分裂しない。DSU(Union-Find)は成分の代表を管理し、追加辺の両端が別成分なら併合する。この例の最後の辺では併合せず、辺数を持つ場合だけ3へ増やす。具体的な更新はDSUの子単元で追う。
- 同じ成分かに加えて、頂点の値の差を知りたい。 例えば値を とし、辺が 、 を指定するなら、 まで分かる。普通のDSUの代表だけではこの5を保持できない。全制約が先にあるなら静的なポテンシャル伝播、制約の追加と差の質問が交互に来るなら重み付きDSUへ進む。ここでのポテンシャルとは、根を基準にした頂点の相対値である。
連結性と到達性を同一視できるのは、ここでは辺が無向だからである。有向辺 では1から2へ進めても、2から1へは戻れない。向きを無視してDSUで併合しても、有向の到達性には答えられない。相互に到達可能な頂点をまとめる強連結成分は別の単元で扱う。
成立条件と計算量
頂点数を 、辺数を とする。静的な無向グラフの成分番号は、全成分を探索して時間 、隣接リストを含む空間 で求められる。辺追加と連結性の質問を繰り返すならDSUを使い、頂点数や黒数など、質問に必要な集約値を代表に持たせる。操作と計算量の詳細は子単元で学ぶ。
成分番号や代表が分かっても、成分内部の経路や距離は復元できない。また、辺の削除で成分が分裂する場合は、普通のDSUでは対応できない。ABC229 Eの解説のように全操作が先に分かるなら、逆順にして削除を追加へ変えられないかを考える。
下位単元
- DSUによる連結成分管理・縮約 — 緑色
- 静的graph等式制約のpotential伝播 — 水色
- potential・weighted DSU — 青色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC218 E「Destruction」 公式問題
技能・出典
主題: cut・cycle性質から最適全域木を構成する(cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: DSUによる連結成分管理・縮約
- ABC229 E「Graph Destruction」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: DSUによる連結成分管理・縮約
- ABC233 F「Swap and Sort」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 構成解・witness復元 / 補助タグ: DSUによる連結成分管理・縮約
- ABC235 E「MST + 1」 公式問題
技能・出典
主題: Kruskal順の閾値DSU sweep(同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: Kruskal順の閾値DSU sweep / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC239 F「Construct Highway」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 構成解・witness復元 / 補助タグ: DSUによる連結成分管理・縮約
- ABC250 Ex「Trespassing Takahashi」 公式問題
技能・出典
主題: Kruskal順の閾値DSU sweep(同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。)。追加で学ぶ技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC264 E「Blackout 2」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: DSUによる連結成分管理・縮約
- ABC270 F「Transportation」 公式問題
技能・出典
主題: cut・cycle性質から最適全域木を構成する(cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: 有界全列挙・有限case分解、DSUによる連結成分管理・縮約
- ABC286 G「Unique Walk」 公式問題
技能・出典
主題: Euler trail・circuit(無向graphでは辺を持つ部分の連結性と奇数次数頂点数が0または2であることを調べ、有向graphでは辺を持つ部分の弱連結性と入次数・出次数の差(trailなら始点+1、終点−1、他0、circuitなら全頂点0)を調べ、全辺を一度ずつ使うtrail・circuitの存在を判定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: Euler trail・circuit / 補助タグ: DSUによる連結成分管理・縮約
- ABC295 G「Minimum Reachable City」 公式問題
技能・出典
主題: 単調path contraction・DSU jump(一度確定したpath区間を次未処理pointerまたはDSU parentで飛ばし、各頂点を高々一度だけ縮約する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 単調path contraction・DSU jump / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約
- ABC301 Ex「Difference of Distance」 公式問題
技能・出典
主題: lowlinkで橋・関節点を特定する(DFS木の到達時刻とlowlink値を計算し、橋と関節点の判定条件を説明できる。)。追加で学ぶ技能: Kruskal順の閾値DSU sweep(同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: Kruskal順の閾値DSU sweep、lowlinkによる橋・関節点の検出 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC302 Ex「Ball Collector」 公式問題
技能・出典
主題: rollback・DFS入退場の状態復元(更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。)。主タグ: rollback・DFS入退場の状態復元 / 補助タグ: DSUによる連結成分管理・縮約
- ABC311 G「One More Grid Task」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: event・値順のオフライン走査 / 補助タグ: DSUによる連結成分管理・縮約、累積和・差分配列
- ABC314 F「A Certain Game」 公式問題
技能・出典
主題: DSU merge tree・Kruskal reconstruction tree(成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: DSU merge tree・Kruskal reconstruction tree / 補助タグ: 寄与の数え上げと順序交換、DSUによる連結成分管理・縮約、法上の四則演算・高速累乗・逆元、根付き木DP・部分木集約
- ABC328 E「Modulo MST」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: DSUによる連結成分管理・縮約
- ABC349 G「Palindrome Construction」 公式問題主題: 回文半径と左右対称区間を特定する
技能・出典
主題: 回文半径と左右対称区間を特定する(各中心の回文半径を求め、左右対称な区間の成立条件を判定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 回文半径・Manacher / 補助タグ: 構成解・witness復元、DSUによる連結成分管理・縮約
- ABC352 E「Clique Connect」 公式問題
技能・出典
主題: cut・cycle性質から最適全域木を構成する(cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: DSUによる連結成分管理・縮約
- ABC352 F「Estimate Order」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 静的graph等式制約のpotential伝播(辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 静的graph等式制約のpotential伝播
- ABC355 F「MST Query」 公式問題
技能・出典
主題: cut・cycle性質から最適全域木を構成する(重み閾値以下のグラフの成分数からMST重みを層別和として導き、辺追加時に各閾値の連結性を更新して最適重みを維持できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: DSUによる連結成分管理・縮約
- ABC364 F「Range Connect MST」 公式問題
技能・出典
主題: cut・cycle性質から最適全域木を構成する(cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約、ordered set・multisetの動的順序管理
- ABC376 G「Treasure Hunting」 公式問題
技能・出典
主題: 01 on Tree・親先行順序のcluster縮約(親先行制約下の交換比較をcluster統計へまとめ、01 on Treeの縮約貪欲で最適順序を構成できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 01 on Tree・親先行順序のcluster縮約 / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論、priority queue・best-first列挙
- ABC383 E「Sum of Max Matching」 公式問題
技能・出典
主題: Kruskal順の閾値DSU sweep(同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: Kruskal順の閾値DSU sweep / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論
- ABC394 G「Dense Buildings」 公式問題
技能・出典
主題: parallel binary search・多数境界の判定共有(各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: parallel binary search・多数境界の判定共有 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査、単調境界探索
- ABC408 E「Minimum OR Path」 公式問題
技能・出典
主題: bitwise greedyによるmask最適化(上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: bitwise greedyによるmask最適化 / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論
- ABC409 F「Connecting Points」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 有界全列挙・有限case分解、DSUによる連結成分管理・縮約
- ABC413 G「Big Banned Grid」 公式問題
技能・出典
主題: 平面graph双対・cut/path対応(埋め込みのfaceをdual頂点へ写し、primal cutとdual path/cycleの対応から最小cut問題を最短路へ変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 平面graph双対・cut/path対応 / 補助タグ: DSUによる連結成分管理・縮約
- ABC440 G「Haunted House」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。)。主タグ: DPの最小十分状態 / 補助タグ: DSUによる連結成分管理・縮約
- ABC447 E「Divide Graph」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: 貪欲法と交換論 / 補助タグ: DSUによる連結成分管理・縮約
- ABC451 F「Make Bipartite 3」 公式問題主題: 二部彩色と成分構造を扱う
技能・出典
主題: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。既習技能: DSUによる連結成分管理・縮約(成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。) / small-to-large・DSU on Tree(小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 二部グラフの彩色と成分構造 / 補助タグ: DSUによる連結成分管理・縮約、small-to-large・DSU on Tree
- ABC466 G「Segment Sum Constraints」 公式問題
技能・出典
主題: 繰り上がり・借り・混合基数を状態にするDP(整除鎖の端数または加算式を下位桁から処理し、切り上げ・切り下げや次桁へのcarryだけを状態にした遷移を設計できる。)。追加で学ぶ技能: potential・weighted DSU(DSUの親辺にpotential差を持たせ、経路圧縮時の差の累積と根の併合方向に応じた符号を導出し、オンラインの差制約追加と頂点間差・矛盾のqueryを処理できる。)。
前提・学習成果・出典
導入対象の目安: 緑色(800–1199)。連結成分を単位に情報を管理し、探索と成分併合を使い分ける入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-connectivity
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 距離・訪問順を求める探索、および有向グラフの強連結成分と順序。
根拠
辺追加と色の反転はABC420 E、削除を逆順の追加へ変える境界はABC229 Eの公式問題・個別公式解説を2026年10月27日に再照合した。四頂点の例と手法の比較は本単元の独自の説明である。