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

hamayanhamayan's blog

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

UnionFind

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

【発展的話題】 Dynamic Connectivity

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

問題