Union Find の利用例

• クラスカル法
• 無向グラフの連結成分数取得・二部グラフ判定・閉路検出
  • 参考: グラフ

Union Find の改造

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

メモ

• union find 旧実装