ABC049-D

README

ABC049 D. 連結

Last Change: 2020-05-04 17:14:26.

@2020-05-04

シンプルな問題設定なはずなのに、難しい。 UFを使うことはすぐわかるが、その後の工夫が思いつけそうなのに思いつけない。

UFのRootに着目する。

それぞれのネットワークに対して別々にUF木を作成し、それぞれのRootを調べて配列に持っておく。 ノード i について調べる必要があるのは、 「ノード i の両方のUF木におけるRootが等しいノードの数」ということになる。

この部分の数え上げは、真面目にやると O(n^2) になってしまうが、 実はソートしたり多次元マップを使うと、各ノードについてほぼ定数オーダーで取得できる。

※このような数え上げの計算量削減の方法はあまり経験がないが、最近解いたものだとこのような問題がある。