競技プログラミングにおけるUnionFind問題まとめ [DSU]

UnionFind, DSU

• 連結成分を管理するデータ構造 (解説)
• AtCoder Libraryで実装がある
• 最小全域木の構成でも使われる
• 連結時に成分に入っている情報を併合することもある(要素数とか)
• incremental(併合はできるが、分離はできない)
• (発展だが)永続UnionFindもある
• 森の連結成分は「頂点数-辺数」で求められるテクがある
• ダブリングを用いることで連続区間のマージができるようになる 問題1 問題2

問題

• AtCoder Union Find

連結判定

• ARC032 道路工事
• ABC075 Bridge
• CC Skiing 解説
• ARC097 Equals 解説
• FHC2018 Round1 Ethan Traverses a Tree 解説
• AC Propagating Edges 解説

連結判定+データ

• ARC037 バウムテスト
• AOJ Shopping
• yukicoder No.416 旅行会社
• AOJ 部活動調査 解説
• AC Weights on Vertices and Edges
• ABC120 Decayed Bridges 解説

永続UnionFind

• AGC002 Stamp Rally (永続UnionFind解だとTLEするかも)

森の連結成分は「頂点数-辺数」で求められるテク

• AGC015 Nuske vs Phantom Thnook 解説
• ECR31 Binary Matrix 解説

【発展的話題】 Dynamic Connectivity

• 参考
• セグメント木を2つ持ってセグメント木上でDFSするらしいがさっぱり分からん
• 動的木でそれっぽいことできるのでは？
• CFの記事
• 【競技プログラミング】online dynamic connectivity(削除可能union-find)の作り方を詳しく解説！！！ - Qiita この前見つけた。ちゃんと読んでない

問題

• CF Dynamic connectivity contest
• HR Simple Tree Counting 解説
• CF319 Painting Edges 解説
• AC Weights on Vertices and Edges
• ECR22 Bipartite Checking