ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

ABC120 D - Decayed Bridges

D - Decayed Bridges

解法

グラフの連結性を考えるのに便利な道具として Union-Find木 があります。Union-Find木では「辺を追加して頂点同士を連結にする」という操作が可能ですが、対して今回の問題は「辺を削除して頂点同士を分断する」という操作になっています。辺の削除はUnion-Find木ではできません。

このような時に有効なのが「時間を逆回しにして考える」というテクニックです。問題の操作を逆回しにすると、辺が全くない状態から始まって辺が1本ずつ追加されていくと考えることができます。これならUnion-Find木が使えます。

ということで辺を1本ずつ追加しながら、それぞれの時点での「互いに行き来できない(非連結な)頂点のペア数」を求めることにしましょう。

最初は辺が1本もないので、全てのペアが非連結です。なので非連結なペア数は  \frac{N(N-1)}{2} 個です。

 (A_{i}, B_{i}) を1本足した際、 A_{i} B_{i} が既に連結だった場合は何も起こりません。非連結だった場合は以下の図のように「既に A_{i} と連結な頂点」と「既に B_{i} と連結な頂点」の組み合わせ全てが新しく連結になります。そのためそれぞれの頂点数を掛け算した値だけ、非連結なペア数が減ることになります。

f:id:betrue12:20190303224053p:plain

あとはこれを実装しましょう。それぞれの連結成分に含まれる頂点数を保持する機能を持ったUnion-Find木を用いて、辺を追加するごとに上記のような計算をしていけばよいです。

ACコード

このコードではUnion-Find木の実装の中に、非連結なペアの個数を計算する処理を追加しています。個人的にはこれが楽ですが、分かりにくいようであればmain関数の中で計算しても良いでしょう。

元の問題は「 i 番目の橋を壊した後に  i 番目の答えを計算する」ですが、時間を逆回ししているため「 i 番目の答えを計算してから、 i 番目の辺を追加する」という処理順番になることに注意してください。