考察
切れた電線を順に処理すると、連結成分が分裂して管理しにくい。切断予定はすべて分かっているので、全切断後から電線を逆順に戻そう。すると必要なのは成分の併合だけになる。さらに、どの発電所へ届くかは問われないため、発電所を一つの代表頂点へまとめると、その成分の大きさから通電都市数が分かる。
毎回の探索で、何を繰り返しているか
都市が 個、発電所が 個あり、電線を指定順に一本ずつ切る。都市からどれかの発電所へ到達できれば、その都市は通電している。各切断の直後の通電都市数を求める。
毎回、全発電所からBFSやDFSで到達都市を数えれば正しい。しかし切断が最大50万回もあり、毎回グラフ全体を調べる 時間では足りない。連結成分を更新して使い回したい。
Union-Find(DSU)は二成分をまとめるのは得意だが、普通のDSUは一成分を分けられない。電線が一本切れても、迂回路があれば成分は変わらず、なければ分裂する。切断をDSUの親子関係から直接取り除くこともできない。親子関係は、元の電線をそのまま保存しているわけではないからだ。
ここで、操作がすべて事前に分かることを使う。最後まで切れない電線だけで最終グラフを作り、切った電線を最後のものから戻す。逆向きには成分が分かれず、辺の追加による併合だけになる。
答えを記録するのは、電線を戻す前
都市1〜4、発電所P、Qを持つ独自例を考える。電線は次の五本である。
1 ─ 2 ─ P
│
3 ─ 4 ─ Q
、、 の順に切ると、通電都市数は4、2、0になる。全切断後には都市の辺 と だけが残る。
必要なのは各行の「戻す前」であり、これを元の順に並べれば4、2、0になる。戻した後を保存すると、一つ前の時刻の答えを記録してしまう。
切断を 回行った後のグラフを と呼び、切る電線の番号を とする。逆走査では、辺 を戻す直前の状態が 、直後が である。この対応を先に定めれば、記録のタイミングを迷わず決められる。
「どれかに届く」を、一つの頂点への到達へ変える
逆向きの併合ができても、発電所は複数ある。都市は一個でも発電所に届けばよく、発電所の名前や個数は答えに使わない。この点を利用し、すべての発電所を特殊頂点 一個へ置き換える。
都市の番号はそのまま残す。電線の端点が発電所なら へ写し、都市なら元の都市へ写す。発電所間の電線は自己ループになるが、連結成分を変えないので併合時に無視してよい。こうして 頂点のDSUを使う。
変換により、もともと別の発電所につながっていた都市も一成分になる。たとえば と しかなくても、変換後は とつながる。都市同士の連結関係は変わるが、通電している都市の集合は変わらない。
なぜ通電判定は変わらないのか。元の発電所への経路は、その発電所を へ写せば変換後の経路になる。逆に、都市から に初めて着くまでの経路では、中間はすべて都市であり、最後の辺は元のどれかの発電所への電線だった。その部分を戻せば元のグラフにも通電経路がある。
従って通電都市数は、
で得られる。 の成分に発電所の代表自身が一個含まれるので、それを引く。
全切断後から、辺を一本ずつ復元する
まず電線を番号付きで保存し、切断対象の番号に印を付ける。 都市と特殊頂点 を単独成分で初期化し、印のない電線をすべて併合する。これで全切断後のグラフができる。
次に の順で、以下を行う。
- を回答配列の 番目へ保存する。
- 電線 の両端を変換後の頂点へ写し、DSUで併合する。
最後に回答配列を先頭から出力する。同じ成分内への辺の追加は、サイズを変えない。切断対象はすべて相異なるので、一つの印と一回の復旧で十分である。
典型の発動条件
更新の向きを変え、使えるデータ構造を変える
逆順処理を候補にするのは、全操作が事前に分かり、順方向の操作に対して、逆方向の操作を速く扱える場合である。本問では「削除で分裂する」が「追加で併合する」へ変わり、DSUが使える。
大切なのは、逆関数をそのまま実行することではない。削除後の最終グラフを作り、必要な元の各時点を逆順に再現している。上書きのように元の値を失う操作でも、逆から見て最後に有効な操作を確定する方法がある。逆向きに何が単調になるかを探すとよい。
全質問が分かるだけでは十分でない。辺の追加と削除が混在すると、逆にしても両方が残り、通常のDSUだけでは解けない。終状態を構築できるかと、逆操作が本当に簡単になるかをセットで確認する。
問いに必要な区別だけをグラフへ残す
「どれかの特殊頂点へ到達できるか」だけが必要なら、特殊頂点を一つへまとめることを検討できる。本問ではこの変換が通電判定を保つため、属性の集計をサイズ取得へ落とせた。ただし都市同士の連結や到達先の種類まで保つ変換ではない。
それらの区別が必要なら、元の頂点を残し、成分へ属性を持たせる。本問でも、成分内の都市数 と発電所有無 を持つ方法で解ける。異なる二成分を併合するとき、片方だけ が真なら、偽の側の都市数だけ通電数が増える。両方真ならどちらも既に通電し、両方偽ならまだ通電しないので増分0である。属性は都市数の和と発電所有無の論理和で更新する。
縮約で区別を消す方法と、成分へ属性を足す方法は、必要な問いから選ぶ。本問の主解法では、答えに不要な発電所ごとの区別を消すことで処理を簡潔にした。
問題固有の要素
本問は発電所を「少なくとも一つ」含む成分の都市数だけを問う。この存在判定が、全発電所を一頂点へまとめる根拠である。「何個の発電所へ届くか」「特定の発電所へ届くか」なら同じ変換は使えない。問題文の量化、特に「どれか」と「すべて」の違いを読むことが、モデルを簡単にする手がかりになる。
正当性
各時点で、元のグラフの都市から発電所へ至る経路は、発電所を へ写すことで変換後の経路になる。逆に変換後の都市から への経路を、最初に へ到達するまで取れば、最後の辺を元の発電所への電線に戻せる。途中の都市間の辺も元のグラフに存在する。従って変換前後で通電都市は一致する。
切断されない辺だけを併合した初期DSUは、変換後の の連結成分を表す。辺 を戻す直前に の成分を表しているなら、その時点の の成分サイズから1を引いた値が切断 の直後の答えである。辺を戻して両端を併合すると、ちょうど の成分になる。
この対応を から1まで繰り返せるため、すべての回答は正しい。元の順に出力することで、要求された各切断直後の値が得られる。
実装上の注意
- 電線の端点の組ではなく、入力で付いた電線番号で切断を管理する。縮約後は別々の電線が同じ二頂点を結ぶ場合がある。
- 特殊頂点のサイズを取得するときは、現在の根を経由する。併合で 自身が根でなくなっても、答えはその成分のサイズである。
- 発電所間の辺や同じ成分内の辺を加えても、成分サイズを二重に足さない。DSUの通常の同根判定を使う。
- 逆走査では必ず記録してから復旧する。答えを逆順に蓄積する実装なら、出力前に反転する。
復習の核
- 削除が難しければ、全削除後を作って追加だけにできないか調べる。
- 逆順では「今が元の何回目の操作の前後か」を定義してから回答を保存する。
- 特殊頂点の区別を消す前に、保存したい問いの双方向の対応を確認する。
- DSUに足す属性は問いに合わせる。存在だけなら真偽、個数なら個数を持つ。
計算量と制約
時間
発電所を端点の読込時に特殊頂点へ写し、DSUを 頂点で用意する。切断対象の印付けと電線の走査に 、初期化・全復旧で合計高々 回の併合を行う。経路圧縮とサイズによる併合を使えば、全体で 時間。 は逆Ackermann関数で、成分サイズの取得も根探索の償却時間に含める。
空間
DSUに 、電線一覧と印に 、切断順と回答に 。入力を含め全体で 空間となる。元の全頂点にDSUを用意する成分属性版なら、これに も含む。
制約との対応
、。切断番号は相異なり、全操作が入力で先に得られる。逆順化によって各電線を高々一回追加する処理へ変え、この大きさに対応する。
出典