UnKoder Challenges - XOR Graph
すぎむさんが問題を書いている UnKoder の問題をちょっとずつ解いています。
解いていて面白かった問題を紹介しようと思います。 UnKoder の問題には, このリンクから挑戦することができます。
今回はこの問題セットの中から XOR Graph の解法を紹介しようと思います。
問題概要
$N$ 個の頂点と $ M $ 本の辺からなる無向グラフが与えられる。頂点は $0$ から $N−1$ まで非負整数の番号が振られている。グラフは自己ループや多重辺を含まない。
あなたは, このグラフに何本かの辺を追加し, グラフ全体を連結にしたい。
$x$ 番目の頂点と $y$ 番目の頂点の間に辺を追加するには, $x \bigoplus y$ だけのコストが掛かる。ただし, $\bigoplus$ はビット XOR の記号である。
グラフ全体を連結にするのに必要な総コストの最小値を求めよ。
制約
- $1 \leqq N \leqq 10^5$
- $0 \leqq M \leqq 10^5$
- グラフは自己ループや多重辺を含まない
