DSUによる連結成分管理・縮約

概要

辺を追加するだけの無向グラフでは、別々の連結成分が一つになることはあっても、一つの成分が分裂することはない。そこで各成分に代表を一つ置き、二頂点が同じ代表を持つかで連結性を判定する。これを管理するデータ構造がDSU(Disjoint Set Union、Union-Findとも呼ぶ)である。

成分の頂点数、辺数、黒い頂点の個数などの付加情報も代表へ集めれば、質問のたびに成分内を探索せずに済む。このように成分へ付ける情報を成分metadataと呼ぶ。

考え方

併合する辺と、成分内に増える辺

四頂点に無向辺1–2、2–3、1–3を順に追加する独自例で、成分の頂点数と辺数を追う。頂点4には辺を追加しない。初めは {1}、{2}、{3}、{4} が別々の成分である。辺1–2で {1, 2} が一成分になり、辺2–3で {1, 2, 3} が一成分になる。

表の「辺」は今回追加する辺、「成分数」はグラフ全体の成分数を表す。最後の列は、頂点1の属する成分の「頂点数 / 辺数」である。

辺成分数頂点 / 辺
なし41 / 0
1–232 / 1
2–323 / 2
1–323 / 3

最後の辺は、既に同じ成分にある二頂点を結ぶ。連結性も頂点数も変わらないが、辺数は増える。この区別が、連結性だけでなく成分の属性も管理するときに必要になる。孤立頂点4も、頂点数1・辺数0の成分として残す。

代表を探し、代表どうしをつなぐ

各頂点 v のDSU内の親を parent[v] とする。最初は parent[v] = v として、全頂点をそれぞれの根にする。根だけが成分の集約値を持ち、size[v] = 1、edges[v] = 0 で始める。成分数も頂点数で初期化する。

find(v) は親をたどって根を返す。その途中の頂点の親を根へ直接付け替える操作が経路圧縮である。同じ成分内で親を付け替えるだけなので、所属する成分は変わらない。二頂点 u, v が同じ成分に属する条件は find(u) == find(v) となる。

辺 u–v を追加するときは、まず両端の根 a = find(u)、b = find(v) を求める。

  • 別根なら併合する。 小さい成分の根を大きい成分の根へ付ける。これを union by size と呼ぶ。残す根を a とした場合、更新前の両根の値から size[a] = size[a] + size[b]、edges[a] = edges[a] + edges[b] + 1 とし、成分数を1減らす。頂点集合は重ならず、辺は両成分の内部辺と今回の一本だから、この加算でよい。
  • 同根なら併合しない。 成分数と size[a] は変えず、edges[a] だけ1増やす。同じ集約値を二回足すと、同一成分を二重に数えてしまう。

初めはDSUの各集合とグラフの各成分が一致している。別成分をつなぐ辺を追加すると、その二成分だけが一つになる。同じ成分内に辺を追加しても分割は変わらない。この二場合で上の処理が実グラフの変化と一致するので、以後も代表による連結性判定と集約値の意味が保たれる。

小さい側を大きい側へ付けると、ある頂点の根までの深さが併合で1増えるたび、その頂点を含む成分のサイズは少なくとも倍になる。これが木を深くしすぎない理由であり、経路圧縮も併用すると操作列全体の計算量をさらに抑えられる。

ただし、DSUの親は元グラフの経路を表さない。 小例で1–2の追加時に2を1へ付けたとする。次に2–3を追加すると、根は1と3なので、3の親は1になる。この時点では元グラフに辺1–3はない。最後の1–3を追加すると三角形になるが、DSUの親はその三辺も記録しない。経路や距離が必要なら元の辺を別に持つ。併合履歴も経路圧縮で失われるため、必要ならDSU merge treeとして別途記録する。

黒い頂点の存在を、個数で保持する

ABC420 Eでは、初めは全頂点が白く、辺の追加、指定頂点の白黒の反転、黒い頂点へ到達できるかの質問が与えられる。無向グラフなので、最後の質問は「自分の成分に黒い頂点があるか」と同じである。0本の辺での到達も認めるため、質問の頂点自身が黒い場合も含む。

存在するかだけなら真偽値で答えられるが、その真偽値だけでは色の反転を更新できない。黒い頂点が一つの成分と二つの成分は、どちらも「存在する」となる。しかし一つを白へ戻した後の答えは違う。そこで各頂点の色を color[v] に、各根の成分黒数を blackCount に持つ。最初は全て白、黒数は0である。

先ほどと同じ辺の追加に色の反転を挟むと、黒数は次のように変わる。この表も独自例である。右の二列はそれぞれ頂点1・3が属する成分の黒数を表し、辺2–3の追加後は同じ成分の値を参照する。

操作1の成分3の成分
初期状態00
1と3を黒にする11
辺1–2を追加11
辺2–3を追加22
辺1–3を追加22
1を白に戻す11
3を白に戻す00

孤立頂点4の成分の黒数は、この間ずっと0である。続けて4を黒にすれば、その成分の黒数だけが1になり、{1, 2, 3} の黒数は0のまま変わらない。

別根を併合するときは、更新前の二根の黒数の和を新しい根へ保存する。同根への辺追加では頂点集合が変わらないので、黒数は加算しない。辺数だけが増える場合と区別する。

色を反転するときは、毎回 r = find(v) を求め、白から黒なら blackCount[r] を1増やし、黒から白なら1減らして、color[v] を反転する。根は併合で変わりうるので、頂点 v 自身や以前保存した代表の欄を更新してはいけない。小例では、元は根だった3も併合後は根1の成分に入る。3を白へ戻す際に更新するのは blackCount[1] である。吸収された根の古い集約値は以後参照せず、全て現在の根へ読み書きする。

併合は重ならない二集合の和、色の反転は一頂点分の増減なので、「根の黒数はその成分内の黒い頂点の個数」という不変条件が保たれる。従って、質問には blackCount[find(v)] > 0 で答えられる。孤立頂点にも同じ処理を使える。

縮約で残す辺を決める

複数の頂点を一頂点として扱う操作を縮約という。併合が済んだ時点で全頂点に id[v] = find(v) を付け、残したい元辺の両端をこのIDへ写す。DSUの親を辺として使うのではなく、元の辺を読み直す。代表番号は連番とは限らないので、必要なら異なる代表を列挙して番号を振り直す。

小例の全連結成分を縮約すると、{1, 2, 3} と {4} がそれぞれ一頂点になる。三角形の三辺は全て自己ループへ写り、異なる成分間の辺は一本もない。到達性だけなら三つの自己ループを消せるが、辺数も知りたいなら、縮約前の辺数3を集約値として残すなどの対応が必要である。

一方、同じ三角形で辺1–2だけを使って先に併合し、残る辺を調べるなら、{1, 2}、{3}、{4} が縮約後の頂点になる。辺2–3と1–3はともに {1, 2} と {3} を結ぶ多重辺へ写る。全辺の連結成分を縮約する場合と、選んだ一部の辺だけで成分を作る場合を区別しよう。

到達性だけを残すなら、同じ向き・同じ端点間の多重辺は一本にまとめられる。辺の本数や辺の選び方を数えるなら、多重度を消すと答えが変わる。費用を扱う場合も、目的に応じて最小重みなどを保持する必要があり、単に任意の一本を残してよいとは限らない。自己ループや多重辺を消す前に、縮約後に何を保存したいかを決める。

成立条件と計算量

頂点数を VV、辺追加・色の反転・質問の操作数を合わせて QQ とする。union by sizeと経路圧縮を併用すると、初期化を含む全体の時間は O((V+Q)α(V))O((V+Q)\alpha(V))、空間は O(V)O(V) である。α\alpha は逆Ackermann関数で、実用的な範囲では非常に小さい。一回ごとが最悪定数時間という意味ではなく、操作列全体で評価した償却計算量である。頂点数・辺数・黒数の更新はいずれも定数時間とする。より大きな集合などを成分に持つなら、その併合費用を別に評価する。

縮約グラフも作る場合、元辺の本数を EE とすると、全頂点の代表を求めて全辺を写すまでの時間は O((V+E)α(V))O((V+E)\alpha(V))、元辺と縮約後の辺を含む空間は O(V+E)O(V+E)。ここでは自己ループ・多重辺をそのまま保持してよい。辺をソートして多重辺を除くなら、さらに O(Elog⁡E)O(E\log E) 時間がかかる。

普通のDSUが扱えるのは、集合が併合される変化である。小例で最後の1–3を加える前に2–3を削除すると、{1, 2, 3} は {1, 2} と {3} に分裂するが、DSUにはそれを判断して分け直す情報がない。削除を含む場合は別の工夫が必要になる。ABC229 Eの解説では、頂点と接続辺を削除する操作が全て先に分かるため、逆順処理によって追加だけの問題へ変換する。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。代表と成分サイズを管理し、辺追加による連結性をDSUで処理する。

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

概念上の親: 連結成分を管理し縮約する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dsu-components

DSUによる連結成分管理・縮約

習得する技能

  • 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。
  • 静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: DSU merge tree・Kruskal reconstruction tree、Kruskal順の閾値DSU sweep、potential・weighted DSU、cut・cycle性質から最適全域木を構成する、01 on Tree・親先行順序のcluster縮約。

辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • DSUによる連結成分管理・縮約の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠

辺追加・色の反転・黒い頂点への到達判定はABC420 E、削除を逆順の追加へ変える境界はABC229 Eの公式問題・個別公式解説を2026年10月27日に再照合した。四頂点の辺・色の更新と縮約の例、その不変条件の説明は本単元の独自補足である。