【C#】Union-Findデータ構造を勉強した

今まで聞いて来たけど、実装したことがなかったのでUnion-Findデータ構造について勉強しました。その時のリンク集です

問題

AtCoderの下記問題を解ければUnion-Findデータ構造は理解できたと言えると思います。 atc001.contest.atcoder.jp

リンク

参考にしたサイトとスライドです。

qiita.com

www.slideshare.net

#実装 C#での実装です。 github.com

ポイント

ポイントとして挙げられるのは、スライドのP15でもありますが、経路圧縮を行っている点です。

再帰で計算した根の情報を各頂点の親として指定します。こうすることで、同じグループの頂点は根から1ホップでたどり着くことができます。

return parent[x] = root(parent[x]);