[ABC284 C] Count Connected Components

https://atcoder.jp/contests/abc284/tasks/abc284_c

素集合森の木の数を求める問題。

解き方

1. すべての節を作る
2. 与えられた辺をすべて繋ぐ
3. 根のユニーク数を求める (それが木の数)

木の数は「節数 - 連結回数」でも求めることができる。

間違えやすいところ

森を作るときに「節を先に登録しておかなくても、どうせ辺を作るとき節も一緒に作られるじゃん」という横着な考え方^[1]があり、たしかにそれはそれで便利なときもあるが、この問題のように木の数を知りたい場合には辺に登場しない節も考慮しないといけない。

具体的には A〜C の節と辺 A-B があったとしたとき孤立した C も木にカウントされるようにする。

コード (AC)

N, M = gets.split.collect(&:to_i)                    # => [5, 3]
UV = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2], [1, 3], [4, 5]]
p DisjointSet.new(1..N).unites(UV).tree_count        # => 2

脚注

1. 事前に登録していない節で辺を作ろうとすると例外を投げる実装も見かける