Union Findで集合の要素をたどる

この記事は Competitive Programming Advent Calendar 2015 - Adventar の24日目の記事です。

UnionFindの素朴な実装だと、併合と同じ集合かどうかの判定は出来ても、集合の要素だけを列挙することはできません。 しかし、UnionFindにリストを組み込んで併合の度に更新することで、集合の要素を列挙できるようになります。

next, lastの処理以外は普通のUnionFindです。

gist.github.com

ライブラリ化したものの特に役に立たずお蔵入りしていましたが、 No.416 旅行会社 - yukicoder を解いたときに使ったのでそういえばCPAC 2015で何も書いてなかったしこれでお茶を濁そうかと思い記事にしました。