【C#】Union-Findデータ構造を勉強した
今まで聞いて来たけど、実装したことがなかったのでUnion-Findデータ構造について勉強しました。その時のリンク集です
問題
AtCoderの下記問題を解ければUnion-Findデータ構造は理解できたと言えると思います。 atc001.contest.atcoder.jp
リンク
参考にしたサイトとスライドです。
www.slideshare.net
＃実装 C#での実装です。 github.com
ポイント
ポイントとして挙げられるのは、スライドのP15でもありますが、経路圧縮を行っている点です。
再帰で計算した根の情報を各頂点の親として指定します。こうすることで、同じグループの頂点は根から1ホップでたどり着くことができます。
return parent[x] = root(parent[x]);
