Union-Find

概要

• グラフの連結成分について調べるために使用する
• Union()関数とFind()関数からなる
  • 連結成分同士の結合をUnion()関数で実施する
  • 同じ連結成分に属する頂点はFind()関数で同じ代表点が返ってくる
• Find()関数で経路圧縮すると、ならし計算量がAckerman関数の逆関数になる
  • 実質定数と言ってしまっていいくらい増加が遅い
  • 解説があった

実装

• Find()関数で経路圧縮する
• 各連結成分の代表点にRankを定義して比較することでUnion()時の代表点を決める手法もあるが、今回は単純に頂点のラベルが小さいものを代表点にする

Python3で実装する

メソッドを実装するだけならimportすら不要

Powered by OnlineGDB

Goで実装する

Priority Queueとは違いPython3と比較してもそんなに労力が変わらない