考察
成分の内部をつなぐために必要な辺を残し、それ以外の辺を成分同士の接続へ回す。こうすれば、既につながっている頂点を分断せずに、操作のたびに連結成分を一つ減らせる。
頂点数を 、辺数を 、初期の連結成分数を とする。一回の操作で新しく加える辺は一本なので、成分数を減らせるのは高々一つである。従って、全体を連結にするには少なくとも 回必要になる。この下界を達成するには、取り外しても今ある連結性を壊さない辺を選びたい。
連結性を支える辺と、付け替えてよい辺を分ける
初めは各頂点を別々のDSU成分とし、入力辺を順に調べる。両端が異なる成分なら併合して、その辺を残す。同じ成分なら、既に残した辺だけで両端を行き来できるので、余剰辺として保存する。残した辺の集合を と呼ぶ。 は各初期成分の全域木を合わせた全域森であり、辺数は 本になる。余剰辺の総数は
である。最後の不等式は問題の保証 による。必要な操作数以上の余剰辺が、グラフ全体には必ずある。
余剰辺は成分別に分けず、入力時の辺番号と両端を組にした (edgeID, u, v) を一つの配列へ保存する。まだ使っていない辺は入力時のままなので、操作時にもこの端点を使える。以後は の辺と、一度付け替えた辺を二度と変更しない。これが、残りの余剰辺をどの順に使ってもよい理由になる。
例えば、頂点1に自己ループが二本あり、頂点2、3が孤立しているなら、二本とも頂点1の成分が持つ余剰辺である。一本を頂点2へ、もう一本を頂点3へ付け替えれば二回で連結にできる。余剰辺が各成分にある必要はなく、辺の持ち主が併合されても、残りを同じ配列から取り出せばよい。
別成分は、現在の代表の先頭二つから選べる
余剰辺の残す側の端点を u、付け替える側を v と決める。現在の所属成分は s = find(u) で分かるが、接続先を毎回全頂点から探すと、合計で 時間かかり得る。必要なのは「s 以外の成分を一つ」であり、頂点全体を探す必要はない。
そこで、現在のDSU根だけを双方向リストへ一つずつ置く。全入力辺の分類が終わった後、find(x) == x である頂点番号を列挙して初期化する。節点の番号はDSU根の頂点番号そのものとし、prev[r]、next[r] に根 r の前後の節点を保存する。先頭を head、前後に節点がないことを NIL で表す。
先頭の根が s でなければ、その head を接続先 t にする。先頭が s なら next[head] を使う。二成分以上残っていれば、必ず s と異なる根が得られる。根の番号もその成分内の実際の頂点番号なので、t をそのまま付け替え先として出力できる。
DSUの併合はサイズの小さい成分を大きい成分へ付け、経路圧縮を併用する。ここでは merge(s, t) が併合後の根 r を返すものとする。新しい根は s、t のどちらかなので、残った根の節点はそのままにし、吸収された根だけをリストから除く。常に s が残ると決めつけると、リストに根でない頂点が残ってしまう。
辺番号・旧端点・新端点を操作へ戻す
(edgeID, u, v) の v 側を t へ移す操作の出力は (edgeID, v, t) である。DSU根 s は所属を調べるための番号であり、旧端点として出力するのは保存した v である。操作後、その辺は u と t を結ぶ。
次は、DSUとリストの初期化を終えた後の構成部分を示す擬似コードである。erase は節点の前後を直接つなぎ直すので、探索を必要としない。
erase(d):
p = prev[d]
q = next[d]
if p == NIL: head = q
else: next[p] = q
if q != NIL: prev[q] = p
answer = []
for (edgeID, u, v) in 余剰辺の配列:
if len(answer) == C - 1: break
s = find(u)
t = head
if t == s: t = next[t]
answer.append((edgeID, v, t))
r = merge(s, t)
d = t if r == s else s
erase(d)
各辺は配列から一度だけ取り出す。最後に操作数 を出力し、answer の各組を保存した順に出力する。初めから連結なら なので、操作せず0だけを出力する。
典型の発動条件
全体の余剰辺を使う成分併合
辺の付け替えによる連結化で、残す全域森を先に固定できるときに使う。全域森の外にある未使用辺は、所属成分が併合されても取り外せる。成分別に余剰辺を移し替えず、全体で一つの配列として扱える。
DSUによる操作後の成分管理
一操作ごとに二成分を併合し、次の操作でも現在の所属を知りたいときに使う。さらに別成分を一つ選ぶ必要があるなら、DSU根の集合も持つ。今回のように根の順序を問わず、併合で根が一つ消えるだけなら、双方向リストで選択と削除を定数時間にできる。
問題固有の要素
最小回数の下界は成分数だけで決まり、 が、その下界を達成するだけの余剰辺を全体で保証している。頂点ごとの次数や接続先の制限がないため、余剰辺が一成分へ偏っていても困らない。
別の問題へ持ち帰る視点: 再配線では、取り外せる辺と守る辺を分け、連結性を保ったまま成分数を減らす。ただし、現在は橋でない辺でも、他の辺を除いた後は橋になる場合がある。初めに橋でなかった辺を任意に使い続けることはできない。最後まで残す全域森を固定すれば、未使用の余剰辺を安全に使える。
正当性
各操作の直前に、全域森 と使用済み辺だけからなるグラフが、現在の各連結成分をつないでいることを不変条件とする。最初は が各初期成分をつなぐので成立する。未使用の余剰辺はこのグラフに含まれず、その両端も でつながっているため、取り外しても現在の成分を分断しない。
DSU根のリストは、初期化時には全成分の根を一つずつ持つ。併合後に返された根を残し、吸収された根だけを削除するので、この性質は保たれる。二成分以上ある間は、先頭またはその次から必ず異なる成分の根 t を選べる。従って (edgeID, v, t) は実際の旧端点を別成分の頂点へ移す合法な操作であり、辺 u-t によって二成分が一つになる。この辺を使用済みとして残せば、不変条件も次の操作へ引き継がれる。DSUの併合後の成分は、実グラフの成分と一致する。
余剰辺は全部で 本あり、一回の操作で一本だけ使うので、連結になる前に使い切ることはない。毎回成分数が一つ減り、ちょうど 回で一成分になる。一操作で減らせる成分数は高々一つなので、この回数は最小である。
実装上の注意
- まず全入力辺を分類し、その後にDSU根のリストを作る。分類途中の根を保存したままにすると、その後の併合で古い根が残る。
merge が新しい根を返さない実装では、併合後に find(s) を呼んで確かめる。erase で先頭を削除するときは head も更新し、NIL を配列の添字として参照しない。
- 自己ループも余剰辺として使える。
u == v でも片端だけを移せばよい。多重辺は辺番号で区別し、各辺は一度しか使わないため、保存した旧端点が変わることはない。
- 初めから連結ならリストの次の節点を参照しない。余剰辺が残っていても、操作数が に達したら終了する。
復習の核
- 「連結成分数を一つ減らす」を下界にしたら、既存の連結性を壊さずに使える辺を探す。
- 一度選んだ余剰辺だけが安全なのでは足りない。全域森と使用済み辺を守り、残る辺も安全に使える不変条件を作る。
- 「別成分が存在する」という証明を、その成分を速く取り出すデータ構造までつなぐ。DSUの代表は併合で変わり得る。
- 小例で出力を確認するときは、操作を実グラフへ適用し、旧端点が合法か、成分数が一つずつ減るかを見る。自己ループ、多重辺、余剰辺の偏りも含める。
計算量と制約
時間
。入力辺の分類に 回、根の列挙に 回、構成に 回のDSU操作を行う。双方向リストの初期化は 、各接続先の選択と根の削除は 、操作列の保存・出力は である。 は逆Ackermann関数であり、サイズによる併合と経路圧縮を併用したDSUの償却計算量に現れる。
空間
。DSUとリストの前後関係に 、余剰辺の配列に 、操作列に を使う。全域森の辺は証明に使う集合であり、実装では別途保存しなくてよい。
制約との対応
公式制約は 、、各辺の端点は1以上 以下の整数である。時間制限は2秒、メモリ制限は1024 MiB。全辺の分類と高々 回の操作で済み、この上限に対応する。自己ループと多重辺を禁止する条件はなく、いずれも同じ手順で扱える。全成分が木なら なので、 と合わせて となり、余剰辺がなくても操作は不要である。
公式問題・個別公式解説を2026年10月27日に再照合した。公式解説の余剰辺による成分併合を基に、全体の配列とDSU根の双方向リストで構成する手順は本稿の独自補足として示した。
出典