Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する

「AさんとBさんは同じチームか？」「このケーブルをつないだら、全社員のPCが1つのネットワークになるか？」——こうしたグループ分けの管理は、素朴に書くと毎回グラフ全体をたどることになり、問い合わせのたびに O(n) かかってしまいます。Union-Find（素集合データ構造 / Disjoint Set Union、略してDSU）は、この「くっつける」と「同じ仲間か調べる」の2つだけに用途を絞り込むことで、1回あたりならしで実質定数時間に近い速度を実現するデータ構造です。この記事では、森（forest）による表現から2つの最適化、計算量の正確な表現、クラスカル法などの応用まで、動くPythonコードで順に整理します。グラフ探索アルゴリズム入門やヒープと優先度付きキュー入門と同じアルゴリズム入門シリーズの1本です。

Union-Findが解く問題 — 動的な連結性とグループ分け

Union-Findが得意とするのは動的連結性（dynamic connectivity）と呼ばれる問題です。要素の集まりがあり、そこに「この2つは同じグループ」という情報が次々に追加されていく状況で、任意の2要素が同じグループかを高速に判定したい、というものです。

具体例を挙げます。

• SNSで友達申請が承認されていくとき、2人が同じ友達クラスタに属するか
• 電力網や通信網にケーブルを追加していくとき、全体が1つにつながったか
• 白黒画像で隣接する黒画素をまとめ、いくつの塊があるか数える（連結成分ラベリング）
• 「a = b」「b = c」といった等式が与えられるとき、矛盾があるかを判定する（同値クラスの管理）

これらは幅優先探索（BFS）や深さ優先探索（DFS）でも解けます。ただしBFS / DFSは「今のグラフ全体を1回なめる」処理なので、辺が1本増えるたびに最初からやり直すと O(V+E) を毎回払うことになります。Union-Findは辺を1本足すコストと問い合わせ1回のコストをどちらも極小に抑えるのが持ち味です。

ここで重要な制約が1つあります。Union-Findは「くっつける」方向にしか進めません。辺を削除したりグループを分割したりする操作（decremental connectivity）は基本的にサポートされません。この非対称性こそが高速さの源です。逆に言うと、削除が必要な問題では素直には使えない、ということでもあります。

森による表現と3つの基本操作 — find / union / same

Union-Findは、各グループを1本の木で表し、全体を森（forest）として持ちます。木の根（root）がそのグループの代表元（representative）です。

実装はとてもシンプルで、parent という配列を1本持つだけです。

• parent[x] == x のとき、x はそのグループの根（代表元）
• そうでないとき、parent[x] は x の親

この表現のうえで、次の3つの操作を定義します。

• find(x): x から親をたどって根に到達し、代表元を返す
• union(x, y): x の根と y の根を求め、片方をもう片方にぶら下げて2つのグループを1つにする（教科書では MakeSet / Union / Find と呼ばれます）
• same(x, y): find(x) == find(y) かどうかで、同じグループかを判定する

大事なのは木の形そのものには意味がないという点です。誰が誰の親かは実装の都合であって、「同じ根に到達するかどうか」だけが意味を持ちます。二分探索木のように順序を保つ必要がないので、木は好きな形に組み替えてよく、これが後述の経路圧縮を許します。

素朴な実装とその弱点 — 木が一直線に伸びると O(n)

まずは最適化を入れない素朴な実装を書いてみます。

class NaiveUnionFind:
    def __init__(self, n):
        self.parent = list(range(n))        # 最初は全員が自分自身を親にする（n個のバラバラな集合）
 
    def find(self, x):                      # x が属する集合の代表元（根）を返す
        while self.parent[x] != x:          # 根に着くまで親をたどる
            x = self.parent[x]
        return x
 
    def union(self, x, y):                  # x の集合と y の集合を併合する
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                    # すでに同じ集合なら何もしない
        self.parent[ry] = rx                # 根 ry を 根 rx にぶら下げる
        return True
 
    def same(self, x, y):                   # 同じ集合に属するか
        return self.find(x) == self.find(y)
 
 
uf = NaiveUnionFind(5)
uf.union(0, 1)
uf.union(3, 4)
print(uf.same(0, 1))
print(uf.same(1, 3))
uf.union(1, 4)
print(uf.same(0, 3))

実行結果は次の通りです。

True
False
True

union(1, 4) によって {0,1} と {3,4} が1つになり、same(0, 3) が True に変わりました。ここまでは意図通りに動いています。

問題は木の形が入力次第で最悪になることです。次のように呼び出すと、木がリンクリストのように一直線に伸びてしまいます。

worst = NaiveUnionFind(6)
for i in range(5):
    worst.union(i + 1, i)
print(worst.parent)
print(worst.find(0))

[1, 2, 3, 4, 5, 5]
5

parent を見ると 0 -> 1 -> 2 -> 3 -> 4 -> 5 と一列に並んでいます。この状態で find(0) を呼ぶと5回さかのぼることになり、要素数 n に対して O(n) です。せっかくデータ構造を用意したのに、線形探索と変わらない速度になってしまいました。

木の高さが伸びる原因は2つあります。(1) 一度たどった長い経路を毎回たどり直していること、(2) どちらの木をどちらにぶら下げるかを何も考えていないこと。この2つにそれぞれ対策を打つのが、次に見る2つの最適化です。計算量の記法そのものが不安なら、先に計算量とBig-O記法 入門を読んでおくと以降の議論が追いやすくなります。

2つの最適化 — 経路圧縮とunion by size

経路圧縮（path compression）

経路圧縮は、find で根までたどったついでに、経路上のノードを全部まとめて根の直下につなぎ替える最適化です。

圧縮前:  0 -> 1 -> 2 -> 3 -> 4 -> 5(根)
 
find(0) を呼ぶと
 
圧縮後:  0, 1, 2, 3, 4 がすべて 5 を直接指す

前述の通り木の形に意味はないので、根が変わらない限り自由につなぎ替えられます。1回の find はたしかに経路の長さぶんの時間がかかりますが、その代わり次回以降の同じ経路が1ステップで終わるようになります。この「一度払えば後が安い」構造こそ、ならし計算量（amortized complexity）で評価すべき典型例です。

似た手法にpath splitting（各ノードの親を祖父に付け替える）とpath halving（1つおきに祖父へ付け替える）があります。どちらも根を2回たどる必要がなく1パスで済み、漸近的な計算量は経路圧縮と同じです。実際、SciPyの DisjointSet は path halving を採用していると公式ドキュメントに明記されています。

union by size / union by rank

もう1つの最適化は、併合の向きを賢く決めることです。

• union by size: 要素数が少ない木の根を、多い木の根にぶら下げる
• union by rank: 木の高さの上界（rank）が小さい木の根を、大きい木の根にぶら下げる

どちらも狙いは同じで、「小さい方を大きい方にぶら下げれば、木の高さが増えにくい」という発想です。この最適化だけでも木の高さは O(log n) に抑えられます。実装のしやすさでは size の方が直感的（そのままグループの要素数として使える）で、rank は経路圧縮と併用すると実際の高さとずれていく点に注意が必要ですが、計算量の議論では上界として機能するので問題ありません。

なお、rankは経路圧縮によって実際の高さより大きくなり得ますが、減らす必要はありません。あくまで高さの上界を保っていればよいからです。

完成版の実装

2つを組み合わせた実装が次のものです。実務でUnion-Findと言えばだいたいこれを指します。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # parent[x] == x なら x は根（代表元）
        self.size = [1] * n            # 根に対してのみ意味を持つ、その集合の要素数
        self.count = n                 # 集合（連結成分）の個数
 
    def find(self, x):
        root = x
        while self.parent[root] != root:      # まず根を見つける
            root = self.parent[root]
        while self.parent[x] != root:         # もう一度たどって、途中のノードを根に直結（経路圧縮）
            self.parent[x], x = root, self.parent[x]
        return root
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)   # 必ず代表元どうしで比べる
        if rx == ry:
            return False                      # すでに同じ集合
        if self.size[rx] < self.size[ry]:     # 小さい木を大きい木にぶら下げる（union by size）
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        self.count -= 1
        return True
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def group_size(self, x):
        return self.size[self.find(x)]        # x が属する集合の要素数
 
 
uf = UnionFind(7)
for a, b in [(0, 1), (1, 2), (3, 4)]:
    uf.union(a, b)
 
print(uf.same(0, 2))        # 0-1-2 はつながっている
print(uf.same(0, 3))        # 0 と 3 は別グループ
print(uf.group_size(2))     # {0,1,2} の大きさ
print(uf.count)             # 連結成分の個数 {0,1,2} {3,4} {5} {6}
 
uf.union(2, 4)              # 2つのグループを併合
print(uf.same(0, 3))
print(uf.group_size(0))
print(uf.count)

True
False
3
4
True
5
3

find を再帰で書くこともできますが、要素数が大きいとPythonでは再帰上限に達しやすいため、上記のようなループ版が安全です。また union が True / False を返す設計にしておくと、「実際に併合が起きたか」がそのまま「閉路ではなかったか」の判定になり、後述のクラスカル法やサイクル検出がとても短く書けます。

count を持たせておくと、連結成分の個数が O(1) で取れます。union が成功するたびに集合が1つ減るので、初期値 n から引いていくだけです。

計算量 — ならし O(α(n)) の意味と出典

Union-Findの計算量は、最適化の組み合わせによってはっきり変わります。

いくつか正確に押さえておきたい点があります。

(1) 経路圧縮とunion by rank / sizeを併用した場合。n 回の MakeSet を含む m 回の操作全体で Θ(m α(n)) になります（α は逆アッカーマン関数）。この O(m α(m, n)) という上界を最初に証明したのがRobert Tarjan（1975年）の論文 "Efficiency of a Good But Not Linear Set Union Algorithm"（Journal of the ACM 22(2), pp.215-225）です。同論文は下界も併せて示しており、この計算量が漸近的にタイトであることを述べています。その後Tarjan と Jan van Leeuwen（1984年）の "Worst-case analysis of set union algorithms"（Journal of the ACM 31(2), pp.245-281）が、path splitting や path halving を含むさまざまな組み合わせについて最悪時解析を与えました。

(2) 「実質定数」と言ってよいのか。逆アッカーマン関数 α(n) は極端に増加が遅く、Wikipediaの記述によれば「現実の宇宙で書き下せるどんな n に対しても4以下」です。したがって実用上は定数と見なせますが、厳密には定数ではありません。記事や資料で O(1) と書かれているものを見かけますが、正しくはならし O(α(n)) です。この記事でもその表記に統一します。

(3) これ以上速くはできないのか。Fredman と Saks は、任意の素集合データ構造が1操作あたりならしで Ω(α(n)) 語のアクセスを必要とすることを示しました（O(log n) ビット語のセルプローブモデル）。つまり Tarjan の上界はこのモデルで最適です。

(4) 経路圧縮のみ、union by rankのみの場合。Wikipediaは、経路圧縮のみ（union by rank / sizeなし）の場合について Θ(n + f (1 + log_{2+f/n} n)) という式を挙げています（n が MakeSet の回数、f が Find の回数）。対数の底が操作の比率に依存する形で、f が n と同程度なら実質的に対数オーダーです。一方、union by rankのみで経路圧縮なしの場合は、m 回の操作で Θ(m log n) です。片方だけでは α(n) には届かず、2つを併用して初めて到達するという点が重要です。

教科書での扱いとしては、『アルゴリズムイントロダクション』（CLRS）が素集合データ構造に1章を割いており、第3版では第21章、第4版では第19章が "Data Structures for Disjoint Sets" にあたります。逆アッカーマン関数を用いた解析はここに詳しく載っています。

なお、ここでいう「ならし（amortized）」は操作列全体を通した平均であって、個々の操作の最悪時間ではありません。経路圧縮が発生する1回の find は経路の長さぶん時間がかかります。リアルタイム性が要求される場面ではこの点に注意してください。

応用1: クラスカル法で最小全域木を求める

Union-Findの最も有名な応用が、最小全域木（MST）を求めるクラスカル法（Kruskal's algorithm）です。手順は驚くほど短くまとまります。

1. 全部の辺を重みの昇順にソートする
2. 軽い辺から順に見て、その辺の両端が別のグループなら採用して union する
3. 同じグループならその辺は閉路を作るので捨てる

「閉路を作るかどうか」の判定がまさに same であり、union の戻り値がそのまま使えます。

def kruskal(n, edges):
    uf = UnionFind(n)
    total, mst = 0, []
    for w, u, v in sorted(edges):        # 重みの小さい辺から順に見る
        if uf.union(u, v):               # 閉路にならない（=別グループ）なら採用
            total += w
            mst.append((u, v, w))
    return total, mst
 
 
edges = [
    (4, 0, 1), (8, 0, 7), (11, 1, 7), (8, 1, 2),
    (7, 7, 8), (1, 7, 6), (6, 8, 6), (2, 8, 2),
    (2, 6, 5), (4, 2, 5), (7, 2, 3), (14, 3, 5),
    (9, 3, 4), (10, 5, 4),
]
total, mst = kruskal(9, edges)
print(total)
print(mst)

37
[(7, 6, 1), (6, 5, 2), (8, 2, 2), (0, 1, 4), (2, 5, 4), (2, 3, 7), (0, 7, 8), (3, 4, 9)]

頂点9個に対して採用された辺が8本、全域木の条件（頂点数マイナス1本）を満たしています。

計算量は辺のソートが支配的で O(E log E) です。Union-Find部分は O(E α(V)) にすぎません。つまりクラスカル法の速さは、ソートアルゴリズム入門で扱ったソートの効率と、Union-Findの軽さの合わせ技で成立しています。

MSTのもう1つの定番であるプリム法は優先度付きキューを使うので、こちらはヒープと優先度付きキュー入門の応用例です。「辺を軽い順に見るクラスカル ＝ Union-Find」「頂点を近い順に伸ばすプリム ＝ ヒープ」と対にして覚えると整理しやすくなります。

応用2: 連結成分の数え上げ・島の数・サイクル検出

連結成分の数え上げ

前掲の実装では count を持たせてあるので、辺を全部 union したあとに uf.count を見るだけで連結成分の個数が分かります。グラフを構築せず、辺のリストを流し込むだけで済むのが利点です。

グリッド上の島の数

2次元グリッドで、上下左右に隣接する陸地（1）をひとつながりの島と数える問題も、Union-Findの典型です。(i, j) を i * w + j という1次元の番号に潰してから使います。

def count_islands(grid):
    h, w = len(grid), len(grid[0])
    uf = UnionFind(h * w)
    land = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] != 1:
                continue
            land += 1
            for di, dj in ((-1, 0), (0, -1)):    # 上と左だけ見れば全ペアを網羅できる
                ni, nj = i + di, j + dj
                if 0 <= ni < h and 0 <= nj < w and grid[ni][nj] == 1:
                    uf.union(i * w + j, ni * w + nj)
    roots = {uf.find(i * w + j) for i in range(h) for j in range(w) if grid[i][j] == 1}
    return len(roots), land
 
 
grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1],
]
print(count_islands(grid))

(3, 7)

島が3つ、陸地のマスが合計7つと正しく数えられました。ここでのコツは上と左だけを見ることです。左上から順に走査していけば、右と下の隣接ペアは相手側の番になったときに処理されるので、判定回数が半分で済みます。

同じ問題はDFSやBFSでも解けますが、Union-Findなら「陸地を1マスずつ追加していく」ような逐次更新にそのまま対応できるのが強みです。

サイクル検出

無向グラフに閉路があるかどうかも、union の戻り値だけで判定できます。

def has_cycle(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):       # 併合できない = 両端がすでに同じ集合 = 閉路
            return True
    return False
 
 
print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))
print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))

False
True

ただしこの手法が使えるのは無向グラフだけです。有向グラフの閉路検出には、DFSで訪問中のノードを管理する方法やトポロジカルソートを使います。

そのほかの応用

• 同値クラスの管理: 「a と b は等しい」という制約を次々に受け取り、矛盾を検出する
• オフラインクエリ: 辺の削除を含むクエリは、時系列を逆から処理して「削除」を「追加」に読み替えると、Union-Findで扱えるようになることがあります
• Tarjanのオフラインの最小共通祖先（LCA）アルゴリズム: クエリをまとめて受け取れる前提で、DFSとUnion-Findを組み合わせてLCAを求めます
• 連結成分ラベリング: 画像処理で、隣接画素をまとめて塊にラベルを振る

重み付きUnion-Find — 「差」を管理する

Union-Findを一歩進めると、「同じグループか」だけでなく「2要素の値の差はいくつか」まで管理できます。これが重み付きUnion-Find（ポテンシャル付きUnion-Find）です。

アイデアは、各ノードに「親との差」を持たせることです。diff[x] を「x の値」引く「親の値」と定義しておくと、根までの diff を足し上げれば「根から見た x の相対値」が求まります。同じグループの2要素 x, y の差は、それぞれの相対値の引き算で得られます。経路圧縮するときは、つなぎ替えと同時に diff も累積値に更新する必要があります。

class WeightedUnionFind:
    """weight(y) - weight(x) = w という関係だけを覚えていく Union-Find"""
 
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.diff = [0] * n            # diff[x] = 「x の値」-「親の値」
 
    def find(self, x):
        path = []
        while self.parent[x] != x:     # 根までの経路を覚えておく
            path.append(x)
            x = self.parent[x]
        root = x
        acc = 0
        for node in reversed(path):    # 根に近い側から累積して経路圧縮
            acc += self.diff[node]
            self.parent[node] = root
            self.diff[node] = acc
        return root
 
    def weight(self, x):               # 根から見た x の相対値
        self.find(x)
        return self.diff[x]
 
    def diff_of(self, x, y):           # 「y の値」-「x の値」（同じ集合のときのみ意味がある）
        return self.weight(y) - self.weight(x)
 
    def union(self, x, y, w):          # 「y の値」-「x の値」= w という情報を追加する
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return self.diff_of(x, y) == w      # 既知の情報と矛盾しないかを返す
        # 根 ry を 根 rx にぶら下げるときの、ry の相対値
        d = self.weight(x) + w - self.weight(y)
        if self.size[rx] < self.size[ry]:       # 小さい方をぶら下げる（向きが反転するので d も反転）
            rx, ry, d = ry, rx, -d
        self.parent[ry] = rx
        self.diff[ry] = d
        self.size[rx] += self.size[ry]
        return True
 
 
wuf = WeightedUnionFind(5)
print(wuf.union(0, 1, 3))      # 1 は 0 より 3 大きい
print(wuf.union(1, 2, 5))      # 2 は 1 より 5 大きい
print(wuf.diff_of(0, 2))       # よって 2 は 0 より 8 大きい
print(wuf.union(0, 2, 8))      # 既知の情報と一致するので True
print(wuf.union(0, 2, 7))      # 矛盾しているので False
print(wuf.diff_of(2, 0))

True
True
8
True
False
-8

「1 は 0 より 3 大きい」「2 は 1 より 5 大きい」という2つの情報だけから、「2 は 0 より 8 大きい」を導けています。さらに、あとから矛盾する情報（7 大きい）が来たときにそれを検出できています。

同じ枠組みの特殊ケースとして、差を0か1（偶奇）に限定すると二部グラフ判定になります。「この2人は敵対している」という情報を積み重ねて矛盾を見つける、といった問題がこれで解けます。

各言語の標準ライブラリ状況

Union-Findは実装が数十行で済むこともあり、標準ライブラリに用意されていない言語が多いのが実情です。2026年7月時点で公式ドキュメントを確認した範囲では、次のようになります。

Pythonで手軽に使いたい場合、SciPy 1.6.0以降に追加された DisjointSet が便利です。公式ドキュメントによれば find は path halving、merge は merge by size を実装しています。

from scipy.cluster.hierarchy import DisjointSet
 
ds = DisjointSet([0, 1, 2, 3, 4])
ds.merge(0, 1)
ds.merge(1, 2)
ds.merge(3, 4)
 
print(ds.connected(0, 2))   # 同じグループか
print(ds.connected(0, 3))
print(ds.subset(0))         # 0 が属する集合
print(ds.subset_size(0))    # その大きさ
print(ds.n_subsets)         # 集合の個数
print(ds.subsets())         # 全部の集合

True
False
{0, 1, 2}
3
2
[{0, 1, 2}, {3, 4}]

C++では、Boost Graph Libraryの boost/pending/disjoint_sets.hpp に disjoint_sets があります。公式ドキュメントに「union by rank と path compression のヒューリスティックで高速化している」と明記されており、同ライブラリの kruskal_minimum_spanning_tree() がその典型的な利用例です。

とはいえ、Union-Findは自作が現実的な選択肢になる数少ないデータ構造でもあります。本体は配列1〜2本、コードは30行程度で、問題ごとに count や group_size を足すといったカスタマイズも簡単です。ハッシュテーブル入門で扱ったような、標準実装をそのまま使うべきデータ構造とは事情が違います。

よくある落とし穴

Union-Findで初学者がつまずきやすいポイントを挙げます。

• find を通さずに parent を直接比較する: parent[x] == parent[y] で同じグループかを判定してはいけません。同じグループでも親が違うことは普通にあります。必ず find(x) == find(y) で比べます
• union の中で代表元を取り忘れる: parent[y] = x のように、根ではない要素をそのままつなぐと木構造が壊れます。必ず rx = find(x), ry = find(y) を取ってから parent[ry] = rx とします
• size や rank を根以外で参照する: これらの配列は根に対してのみ意味を持ちます。グループの大きさを知りたいなら size[find(x)] です
• 削除やグループの分割ができない: 標準的なUnion-Find（森）は要素の削除に向きません。Wikipediaも「要素の削除に対して好意的に振る舞わない」と述べています（削除を定数時間で扱う現代的な変種の存在にも触れられています）。分割が必要なら、オフラインで時系列を逆にたどるといった別の設計を検討してください
• Undo / ロールバックと経路圧縮は両立しない: 併合を巻き戻せるDSU（rollback付きDSU）を作りたい場合、経路圧縮は使えません。経路圧縮はならし計算量に依存した最適化なので、巻き戻すと計算量の保証が壊れるためです。union by rank / size のみで実装し、1操作 O(log n) を受け入れるのが定石です
• find の再帰実装でスタックが溢れる: Pythonでは既定の再帰上限が浅く、要素数が大きいと RecursionError になります。ループで書くのが安全です
• α(n) を O(1) と書いてしまう: 実用上は定数と見なせますが、厳密には定数ではありません。技術文書では「ならし O(α(n))」と書くのが正確です
• 0-indexed と 1-indexed の混在: 問題文が1始まりの頂点番号なのに配列を0始まりで作り、n 番目にアクセスして落ちる、というのはよくあるミスです

考え方の型として、Union-Findは「状態を持ち回して逐次更新する」タイプのアルゴリズムです。部分問題の答えを積み上げていく動的計画法（DP）入門と合わせて押さえておくと、問題を見たときの引き出しが増えます。

まとめ

• Union-Find（素集合データ構造 / DSU）は、要素のグループ分けを管理し「くっつける（union）」「同じ仲間か（same）」を高速に処理するデータ構造。削除や分割はできないという制約と引き換えに速さを得ている
• 各グループを木で表し、根が代表元。実装は parent 配列1本が基本で、parent[x] == x が根の目印
• 素朴な実装は木が一直線に伸びて最悪 O(n)。経路圧縮とunion by size / rankの2つの最適化で解消する
• 両方を併用したときのならし計算量は O(α(n))（逆アッカーマン関数）。Tarjan（1975年）が示した結果で、Fredman と Saks の下界により最適。O(1) ではなく O(α(n)) と書くのが正確。片方だけでは O(log n) 系にとどまる
• 応用は幅広く、クラスカル法、連結成分の数え上げ、グリッドの島の数、無向グラフのサイクル検出、同値クラスの管理、重み付きUnion-Findによる差の管理など
• Python / C++ / Java / Go / JavaScript / Rust いずれも標準ライブラリにはなく、SciPyやBoost、あるいは自作で対応する

まずは parent 配列だけの素朴な実装を書き、手で union を何度か呼んで木の形が伸びていく様子をトレースしてみてください。そのうえで経路圧縮を入れると、配列の中身が一気に平らになる瞬間が見えます。この体験があると、α(n) という不思議な計算量の正体にも納得がいくはずです。

参考リンク

• Disjoint-set data structure - Wikipedia
• Efficiency of a Good But Not Linear Set Union Algorithm（Tarjan 1975, J. ACM 22(2): 215-225）
• Disjoint Set Union - Algorithms for Competitive Programming
• scipy.cluster.hierarchy.DisjointSet（SciPy公式ドキュメント）
• Boost Disjoint Sets（Boost Graph Library公式ドキュメント）
• Ackermann function - Wikipedia（逆アッカーマン関数）
• Kruskal's algorithm - Wikipedia
• Offline Deletion - USACO Guide（rollback付きDSU）