連結成分を管理し縮約する

概要

無向グラフで辺を何本かたどって行き来できる頂点を、ひとまとまりの連結成分として扱う。同じ成分に属するかだけで答えが決まるなら、質問のたびに経路を探す代わりに、成分の番号や代表を調べればよい。さらに、頂点数や黒い頂点の個数を成分ごとに持つと、成分全体についての質問にも答えられる。

この単元では、必要な答えと更新の種類から、静的な探索、辺追加に対する成分併合、頂点間の差の保持を選び分ける。

考え方

四頂点に無向辺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の子単元で追う。
  • 同じ成分かに加えて、頂点の値の差を知りたい。 例えば値を x1,x2,x3x_1,x_2,x_3 とし、辺が x2−x1=2x_2-x_1=2、x3−x2=3x_3-x_2=3 を指定するなら、x3−x1=5x_3-x_1=5 まで分かる。普通のDSUの代表だけではこの5を保持できない。全制約が先にあるなら静的なポテンシャル伝播、制約の追加と差の質問が交互に来るなら重み付きDSUへ進む。ここでのポテンシャルとは、根を基準にした頂点の相対値である。

連結性と到達性を同一視できるのは、ここでは辺が無向だからである。有向辺 1→21\to2 では1から2へ進めても、2から1へは戻れない。向きを無視してDSUで併合しても、有向の到達性には答えられない。相互に到達可能な頂点をまとめる強連結成分は別の単元で扱う。

成立条件と計算量

頂点数を VV、辺数を EE とする。静的な無向グラフの成分番号は、全成分を探索して時間 O(V+E)O(V+E)、隣接リストを含む空間 O(V+E)O(V+E) で求められる。辺追加と連結性の質問を繰り返すならDSUを使い、頂点数や黒数など、質問に必要な集約値を代表に持たせる。操作と計算量の詳細は子単元で学ぶ。

成分番号や代表が分かっても、成分内部の経路や距離は復元できない。また、辺の削除で成分が分裂する場合は、普通のDSUでは対応できない。ABC229 Eの解説のように全操作が先に分かるなら、逆順にして削除を追加へ変えられないかを考える。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

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

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(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日に再照合した。四頂点の例と手法の比較は本単元の独自の説明である。