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

hamayanhamayan's blog

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

UnionFind, DSU

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

【発展的話題】 Dynamic Connectivity

問題