Union Find の利用例

• クラスカル法で最小全域木 を求める
  • 閉路ができないように連結成分を UF で管理する
• 無向グラフの連結成分数取得・二部グラフ判定・閉路検出
  • 参考: グラフ
• だんだんつながっていくシミュレーション

Union Find の改造

• ポテンシャル付き UF
• 同じグループの（可換半群）総積が求められる UF
  • 例
    • 連結成分ごとのノードの添字の最小値
    • 連結成分ごとのノードの値の総和
    • ABC372 E - K-th Largest Connected Components **** (top 10 を保持する)

メモ

• union find 旧実装