はまやんはまやんはまやん

hamayanhamayan's blog

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

UnionFind

  • 連結成分を管理するデータ構造 (解説)
  • 最小全域木の構成でも使われる
  • 連結時に成分に入っている情報を併合することもある(要素数とか)
  • incremental(併合はできるが、分離はできない)
  • (発展だが)永続UnionFindもある
  • 森の連結成分は「頂点数-辺数」で求められるテクがある

問題

連結判定

連結判定+データ

永続UnionFind

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

【発展的話題】 Dynamic Connectivity

  • 参考
  • セグメント木を2つ持ってセグメント木上でDFSするらしいがさっぱり分からん
  • CFの記事

問題