ABC120 D - Decayed Bridges
解法
グラフの連結性を考えるのに便利な道具として Union-Find木 があります。Union-Find木では「辺を追加して頂点同士を連結にする」という操作が可能ですが、対して今回の問題は「辺を削除して頂点同士を分断する」という操作になっています。辺の削除はUnion-Find木ではできません。
このような時に有効なのが「時間を逆回しにして考える」というテクニックです。問題の操作を逆回しにすると、辺が全くない状態から始まって辺が1本ずつ追加されていくと考えることができます。これならUnion-Find木が使えます。
ということで辺を1本ずつ追加しながら、それぞれの時点での「互いに行き来できない(非連結な)頂点のペア数」を求めることにしましょう。
最初は辺が1本もないので、全てのペアが非連結です。なので非連結なペア数は 個です。
辺 を1本足した際、 と が既に連結だった場合は何も起こりません。非連結だった場合は以下の図のように「既に と連結な頂点」と「既に と連結な頂点」の組み合わせ全てが新しく連結になります。そのためそれぞれの頂点数を掛け算した値だけ、非連結なペア数が減ることになります。
あとはこれを実装しましょう。それぞれの連結成分に含まれる頂点数を保持する機能を持ったUnion-Find木を用いて、辺を追加するごとに上記のような計算をしていけばよいです。
ACコード
- (Ruby)Submission #4447426 - AtCoder Beginner Contest 120
- (C++)Submission #4455969 - AtCoder Beginner Contest 120
このコードではUnion-Find木の実装の中に、非連結なペアの個数を計算する処理を追加しています。個人的にはこれが楽ですが、分かりにくいようであればmain関数の中で計算しても良いでしょう。
元の問題は「 番目の橋を壊した後に 番目の答えを計算する」ですが、時間を逆回ししているため「 番目の答えを計算してから、 番目の辺を追加する」という処理順番になることに注意してください。