ABC 392 E — Cables and Servers

考察

成分の内部をつなぐために必要な辺を残し、それ以外の辺を成分同士の接続へ回す。こうすれば、既につながっている頂点を分断せずに、操作のたびに連結成分を一つ減らせる。

頂点数を NN、辺数を MM、初期の連結成分数を CC とする。一回の操作で新しく加える辺は一本なので、成分数を減らせるのは高々一つである。従って、全体を連結にするには少なくとも C−1C-1 回必要になる。この下界を達成するには、取り外しても今ある連結性を壊さない辺を選びたい。

連結性を支える辺と、付け替えてよい辺を分ける

初めは各頂点を別々のDSU成分とし、入力辺を順に調べる。両端が異なる成分なら併合して、その辺を残す。同じ成分なら、既に残した辺だけで両端を行き来できるので、余剰辺として保存する。残した辺の集合を FF と呼ぶ。FF は各初期成分の全域木を合わせた全域森であり、辺数は N−CN-C 本になる。余剰辺の総数は

M−(N−C)=M−N+C≥C−1M-(N-C)=M-N+C\geq C-1

である。最後の不等式は問題の保証 M≥N−1M\geq N-1 による。必要な操作数以上の余剰辺が、グラフ全体には必ずある。

余剰辺は成分別に分けず、入力時の辺番号と両端を組にした (edgeID, u, v) を一つの配列へ保存する。まだ使っていない辺は入力時のままなので、操作時にもこの端点を使える。以後は FF の辺と、一度付け替えた辺を二度と変更しない。これが、残りの余剰辺をどの順に使ってもよい理由になる。

例えば、頂点1に自己ループが二本あり、頂点2、3が孤立しているなら、二本とも頂点1の成分が持つ余剰辺である。一本を頂点2へ、もう一本を頂点3へ付け替えれば二回で連結にできる。余剰辺が各成分にある必要はなく、辺の持ち主が併合されても、残りを同じ配列から取り出せばよい。

別成分は、現在の代表の先頭二つから選べる

余剰辺の残す側の端点を u、付け替える側を v と決める。現在の所属成分は s = find(u) で分かるが、接続先を毎回全頂点から探すと、合計で O(NC)O(NC) 時間かかり得る。必要なのは「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)

各辺は配列から一度だけ取り出す。最後に操作数 C−1C-1 を出力し、answer の各組を保存した順に出力する。初めから連結なら C=1C=1 なので、操作せず0だけを出力する。

典型の発動条件

全体の余剰辺を使う成分併合

辺の付け替えによる連結化で、残す全域森を先に固定できるときに使う。全域森の外にある未使用辺は、所属成分が併合されても取り外せる。成分別に余剰辺を移し替えず、全体で一つの配列として扱える。

DSUによる操作後の成分管理

一操作ごとに二成分を併合し、次の操作でも現在の所属を知りたいときに使う。さらに別成分を一つ選ぶ必要があるなら、DSU根の集合も持つ。今回のように根の順序を問わず、併合で根が一つ消えるだけなら、双方向リストで選択と削除を定数時間にできる。

問題固有の要素

最小回数の下界は成分数だけで決まり、M≥N−1M\geq N-1 が、その下界を達成するだけの余剰辺を全体で保証している。頂点ごとの次数や接続先の制限がないため、余剰辺が一成分へ偏っていても困らない。

別の問題へ持ち帰る視点: 再配線では、取り外せる辺と守る辺を分け、連結性を保ったまま成分数を減らす。ただし、現在は橋でない辺でも、他の辺を除いた後は橋になる場合がある。初めに橋でなかった辺を任意に使い続けることはできない。最後まで残す全域森を固定すれば、未使用の余剰辺を安全に使える。

正当性

各操作の直前に、全域森 FF と使用済み辺だけからなるグラフが、現在の各連結成分をつないでいることを不変条件とする。最初は FF が各初期成分をつなぐので成立する。未使用の余剰辺はこのグラフに含まれず、その両端も FF でつながっているため、取り外しても現在の成分を分断しない。

DSU根のリストは、初期化時には全成分の根を一つずつ持つ。併合後に返された根を残し、吸収された根だけを削除するので、この性質は保たれる。二成分以上ある間は、先頭またはその次から必ず異なる成分の根 t を選べる。従って (edgeID, v, t) は実際の旧端点を別成分の頂点へ移す合法な操作であり、辺 u-t によって二成分が一つになる。この辺を使用済みとして残せば、不変条件も次の操作へ引き継がれる。DSUの併合後の成分は、実グラフの成分と一致する。

余剰辺は全部で M−N+C≥C−1M-N+C\geq C-1 本あり、一回の操作で一本だけ使うので、連結になる前に使い切ることはない。毎回成分数が一つ減り、ちょうど C−1C-1 回で一成分になる。一操作で減らせる成分数は高々一つなので、この回数は最小である。

実装上の注意

  • まず全入力辺を分類し、その後にDSU根のリストを作る。分類途中の根を保存したままにすると、その後の併合で古い根が残る。
  • merge が新しい根を返さない実装では、併合後に find(s) を呼んで確かめる。erase で先頭を削除するときは head も更新し、NIL を配列の添字として参照しない。
  • 自己ループも余剰辺として使える。u == v でも片端だけを移せばよい。多重辺は辺番号で区別し、各辺は一度しか使わないため、保存した旧端点が変わることはない。
  • 初めから連結ならリストの次の節点を参照しない。余剰辺が残っていても、操作数が C−1C-1 に達したら終了する。

復習の核

  • 「連結成分数を一つ減らす」を下界にしたら、既存の連結性を壊さずに使える辺を探す。
  • 一度選んだ余剰辺だけが安全なのでは足りない。全域森と使用済み辺を守り、残る辺も安全に使える不変条件を作る。
  • 「別成分が存在する」という証明を、その成分を速く取り出すデータ構造までつなぐ。DSUの代表は併合で変わり得る。
  • 小例で出力を確認するときは、操作を実グラフへ適用し、旧端点が合法か、成分数が一つずつ減るかを見る。自己ループ、多重辺、余剰辺の偏りも含める。

計算量と制約

時間

O((N+M)α(N))O((N+M)\alpha(N))。入力辺の分類に MM 回、根の列挙に NN 回、構成に O(C)O(C) 回のDSU操作を行う。双方向リストの初期化は O(N)O(N)、各接続先の選択と根の削除は O(1)O(1)、操作列の保存・出力は O(C)O(C) である。α\alpha は逆Ackermann関数であり、サイズによる併合と経路圧縮を併用したDSUの償却計算量に現れる。

空間

O(N+M)O(N+M)。DSUとリストの前後関係に O(N)O(N)、余剰辺の配列に O(M)O(M)、操作列に O(C)O(C) を使う。全域森の辺は証明に使う集合であり、実装では別途保存しなくてよい。

制約との対応

公式制約は 2≤N≤2×1052\leq N\leq 2\times 10^5、N−1≤M≤2×105N-1\leq M\leq 2\times 10^5、各辺の端点は1以上 NN 以下の整数である。時間制限は2秒、メモリ制限は1024 MiB。全辺の分類と高々 N−1N-1 回の操作で済み、この上限に対応する。自己ループと多重辺を禁止する条件はなく、いずれも同じ手順で扱える。全成分が木なら M=N−CM=N-C なので、M≥N−1M\geq N-1 と合わせて C=1C=1 となり、余剰辺がなくても操作は不要である。

公式問題・個別公式解説を2026年10月27日に再照合した。公式解説の余剰辺による成分併合を基に、全体の配列とDSU根の双方向リストで構成する手順は本稿の独自補足として示した。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Cables and Servers の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DSUによる連結成分管理・縮約

主題
  • DSUによる連結成分管理・縮約: 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: DSUによる連結成分管理・縮約

    補助タグ: 構成解・witness復元

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: DSUによる連結成分管理・縮約

    • 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題