Union-Findの実装とパス圧縮の最適化

Union-Find（またはディスジョイントセット）は、要素の集合を管理し、要素同士の関連性を効率的に判断するためのデータ構造です。このデータ構造は、特にグラフの接続成分を管理する際に非常に役立ちます。ここでは、Union-Findの基本的な実装と、パス圧縮という最適化手法について学びます。

Union-Findの基本的な実装

Union-Findは、主に以下の2つの操作を提供します。

1. Find: ある要素が属する集合の代表元を見つける。
2. Union: 2つの集合を統合する。

以下に、Union-Findの基本的な実装を示します。

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # 各要素の親を初期化
        self.rank = [1] * size  # 各要素のランクを初期化

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # パス圧縮
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP != rootQ:  # すでに同じ集合でない場合
            # ランクに基づいて低い木を高い木の子にする
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1  # ランクを増やす

# 使用例
uf = UnionFind(10)
uf.union(1, 2)
uf.union(2, 3)
print(uf.find(1))  # 1の代表元を出力
print(uf.find(3))  # 1の代表元を出力（2と3は1に統合されているため）

コードの解説

• __init__: 初期化メソッドでは、各要素の親を自分自身に設定し、ランクを1に初期化します。
• find: 再帰的に親を辿っていき、最終的な親（代表元）を返します。この時、パス圧縮を行い、経路上の要素の親を直に代表元に設定することで、次回の検索を高速化します。
• union: 2つの要素の代表元を見つけ、異なる集合であれば、ランクに基づいて木を結合します。ランクが同じ場合は、どちらかの木を根にし、ランクを増やします。

パス圧縮の重要性

パス圧縮は、Find操作を高速化するためのテクニックです。このテクニックを用いることで、木の高さを低く保ち、次回のFind操作をより迅速に行うことができます。これにより、Union-Findの操作はほぼ定数時間で実行できるようになります。

Union-Findの性能

Union-Findは、以下のような時間計算量を持っています。

• Find: O(α(n))
• Union: O(α(n))

ここで、α(n)はアッカーマン関数の逆関数で、非常に遅い成長を示します。このため、実用上はほぼ定数時間で操作が行えると考えてよいでしょう。

まとめ

• Union-Findは、要素の集合を管理するための強力なデータ構造です。
• Find操作におけるパス圧縮を使用することで、性能を大幅に向上させることができます。
• Union操作では、ランクを考慮することで木の高さを抑えることができます。

この知識を基に、Union-Findを利用したさまざまな問題に挑戦してみましょう。