Union-Find 木 | アルゴリズムビジュアル大事典

シンボル

データ
ランクrank

集合の合併
指定された2つのノードのそれぞれの根(代表)を求めます。root1 ← findSet(x)
root2 ← findSet(y)
合併する根(代表)を指します。root1, root2
根のランクを比較します。if rank[x] > rank[y]:
選ばれた新しい根(代表)を指します。xまたはy
ランクを1増やします。rank[y]++
親を書き換えます。parent[?] ← ?
経路圧縮を行います。parent[x] ← findSet(parent[x]):

アニメーション

集合の合併
Union-Find 木 | 集合の合併