概要
解法
頂点を削除するとたくさん連結成分が増える可能性があってややこしいので、辺削除の操作に分解します。辺を削除したときに、元の連結成分の大きさがどう変化するかを計算できればよいです。
「Weighted Union Heuristic による集合の分割」をします。よくあるのは合併ですが、今回は分割です。集合 $A$ を $A = B\amalg C$ と分割するときに、
- $B, C$ のうち小さい方を検出する。小さい方が $B$ であるとする。
- 新たに集合 $B$ を作る。集合 $C$ は新たに作らず、$A$ から $B$ を削除したものを $C$ とする。
という要領です。
実際には、
- 各集合の要素数
- 各頂点がどの集合に属するか
を管理すれば十分で、集合そのものを作る必要はありません。
あとは、辺を切ったときにできる連結成分のうち、「小さい方」をどうやって検出するかが問題です。これは、
- $2$ 点からの bfs / dfs を並行して進める
- 先に探索が終わった方が小さい成分
とすればよいです。これは頂点数の小さい連結成分を検出するとは限りませんが、ある頂点集合に対する bfs / dfs の探索回数は、そこに属する頂点の次数の和で評価できます。したがって、頂点数ではなく次数の和を集合の「大きさ」と見なしておけば、小さい方の成分が検出できることになります。
全体の計算量は、$O(N\log N)$ 時間となります。
