Union-Find (連結成分数)｜コードで実践

Union-Find (連結成分数)

このレッスンで分かること

Union-Find は 木の親ポインタだけで集合を表現 する仕組み

素朴な実装でも O(N) 程度

Union-Find (別名 Disjoint Set Union / DSU) は、要素を 互いに素なグループ に分けて管理するデータ構造です

Union-Find とは

Union-Find (Disjoint Set Union) を使い、辺の集合からグラフの連結成分の数を求める関数を実装する。森のような構造でグループを管理する手法を学ぶ。

Union-Find (別名 Disjoint Set Union / DSU) は、要素を 互いに素なグループ に分けて管理するデータ構造です。次の 2 つの操作を高速に行えるのが特徴です。

find(x) ... x が属するグループの代表元を返す
union(x, y) ... x と y を同じグループにマージする

グラフの連結成分判定、最小全域木 (Kruskal 法)、オフラインな連結判定など、応用範囲が非常に広いデータ構造です。本レッスンでは n 個のノードと辺リスト edges を受け取り、連結成分の数 を返す関数を作ります。

Union-Find は 木の親ポインタだけで集合を表現 する仕組み。シンプルなのに驚くほど高速。

仕組み

各ノードに親を 1 つ持たせます。最初は全員が自分自身を親としています (parent[i] = i)。find(x) は親を辿ってルートに行き着くまで上に登る操作です。union(x, y) は 両者のルートを取り、片方をもう片方の子にする ことで合体させます。

diagram (will load when visible)

図のポイント (テキスト併記)

各操作後の グループ数 を数えるには、最後に find(i) を全ノードに対して呼び、ユニークなルートの数を数えれば OK です

各操作後の グループ数 を数えるには、最後に find(i) を全ノードに対して呼び、ユニークなルートの数を数えれば OK です。

計算量

最適化なしの素朴な実装では、木が一直線に退化すると find 1回の最悪ケースが O(N) になります。path compression (find のついでに親をルートに直結する) と union by rank (低い木を高い木の子にする) という最適化を入れると、ほぼ定数時間 O(α(N)) (アッカーマン関数の逆) で動作します。本レッスンでは path compression だけ実装します。

Python での実装

Python

def countComponents(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
    for a, b in edges:
        union(a, b)
    return len(set(find(i) for i in range(n)))

parent 配列で各ノードの親を保持し、初期状態は自分自身を親とします。union で辺ごとに 2 つのノードを 1 グループにし、最後に各ノードのルートを取って ユニークなルート数 を返します。

JavaScript での実装

JavaScript

function countComponents(n, edges) {
  const parent = Array.from({length: n}, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  function union(a, b) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) parent[ra] = rb;
  }
  for (const [a, b] of edges) union(a, b);
  const roots = new Set();
  for (let i = 0; i < n; i++) roots.add(find(i));
  return roots.size;
}

動作例

n = 5、edges = [[0,1], [1,2], [3,4]] の場合

union(0, 1) → parent = [1, 1, 2, 3, 4]
union(1, 2) → parent = [1, 2, 2, 3, 4]
union(3, 4) → parent = [1, 2, 2, 4, 4]

最後に find(0)..find(4) のルートを取ると {2, 2, 2, 4, 4} でユニークは 2 つ。連結成分は {0, 1, 2} と {3, 4} の 2 個になります。

グラフを再帰探索しなくても 連結成分を数えられる。これが Union-Find の威力。

応用例

Kruskal 法 で最小全域木を構築する際、サイクル判定 に使う
動的な連結判定 で、辺が増えていく際に逐次成分数を更新する
アカウント統合 や 画像の連結領域抽出 にも応用される

よくある間違い

1 つ目は path compression を入れない ことです。深い木になると find が遅くなります。parent[x] = parent[parent[x]] という 1 行を入れるだけで劇的に速くなります。2 つ目は union で同じ親を結ぶ こと。ra == rb のときは何もしないように分岐を入れます。3 つ目は 元の辺リストを破壊する こと。読むだけならよいですが、書き換えると呼び出し側が困ります。

やってみよう

union by rank (rank/size 配列) も追加してみる。木の高さがさらに浅くなる。
path compression を再帰版で書いてみる。return parent[x] if parent[x] == x else find(parent[x]) のような形。
「2 つのノードが同じグループに属するか」 を返す connected(a, b) 関数を作ってみる。find(a) == find(b) の判定。

Union-Find は 小さなコード で 大きな問題 を解ける。アルゴリズム上級の入り口にぴったりの題材。

よくある質問

Q. Union-Find はどんな場面で使いますか？

A. グループ分け（クラスタリング）、連結判定、最小全域木（Kruskal 法）などで使います。要素を集合に分類しながら「同じグループかどうか」を高速に判定したいときに最強の構造で、ほぼ O(α(n)) ≒ O(1) で動きます。

Q. 経路圧縮とは何ですか？

A. find 操作中に通ったノードの parent を root に書き換える最適化です。次回からの find が O(1) 近くまで高速化します。union by rank（小さい木を大きい木に繋ぐ）と組み合わせると、ほぼ定数時間で動く理想形になります。

Q. BFS / DFS との使い分けは？

A. 辺の追加が逐次的（オフライン）なら Union-Find、グラフが静的に与えられているなら BFS/DFS でも十分です。Union-Find は「辺を 1 本ずつ足しながら連結判定」のような動的シナリオで真価を発揮します。

次のレッスン

次は 最終総まとめクイズ で、最終総まとめクイズを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

Union-Find の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. Union-Find とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

Union-Find (連結成分数)