AtCoder Library を読んでアルゴリズムを勉強：DSU（union-find） - Qiita

競技プログラミング AtCoder では、コンテストでよく使うアルゴリズムをライブラリにした AtCoder Library (ACL) を公開していて、特に C++ ならコンテスト内で利用できます。 私は Ruby を使っているため直接は利用できず、ライブラリを模写する必要がありました。その過程で学んだアルゴリズムを整理してまとめます。 今回は disjoint set union (DSU) です。 union-find や素集合データ構造の名称のほうが一般的なようです。グラフでのイメージがしやすく、アルゴリズムも読みやすく、勉強していて楽しかった記憶があります。（ACLの模写で最初に選びました） AtCoder Library の dsu ソースコード ドキュメント 参考文献 Zvi Galil and Giuseppe F. Italiano, Data structures an