Union Find(ユニオンファインド)とは?グループを管理するデータ構造

スポンサーリンク
Union Find(ユニオンファインド)とは?グループを管理するデータ構造 データ構造

Union Findとは

Union Findとは、

グループ分けを効率的に管理できるデータ構造

です。

 

主に以下の2つの操作を高速に処理することができます。

  • 2つのグループを統合する
  • 要素が所属するグループを検索する

ただし、グループの統合はできても分割はできません。

 

基本的な構造

ユニオンファインドは、木(ツリー構造) を使ってグループを管理します。

初期状態

最初はすべての要素が自分自身が親になっています。

UnionFindの初期状態

 

UNION操作(統合)

2つの要素を同じグループにする操作です。

要素1と2を同じグループに統合するには、片方の親をもう一方の親にします。

UnionFindの結合

 

FIND操作(統合)

ある要素の親を取得する操作です。

要素2の親は木を辿っていくと親である要素1を見つけることができます。

 

効率を向上させるテクニック

UnionFindを高速化させるため、以下の2つの手法がよく使われます。

経路圧縮

経路途中の要素の親を直接ルートにつなげることで木が浅くなり、検索を高速化することができます。

UnionFindの経路圧縮

 

ランクによる併合

木の高さが低い方を高いほうに繋ぐことで、木の高さを抑えることができます。

UnionFindのランクによる併合

 

実装(Python)

実装

from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.parent = defaultdict(lambda: -1)
        self.rank = defaultdict(int)

    def is_root(self, node):
        return self.parent[node] == -1

    def find(self, node):
        while not self.is_root(node):
            node = self.parent[node] # 経路圧縮
        return node

    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        if root1 == root2:
            return
        if self.rank[root1] < self.rank[root2]:
            smaller, bigger = root1, root2
        else:
            smaller, bigger = root2, root1
        self.parent[smaller] = bigger
        self.rank[bigger] = max(self.rank[bigger], self.rank[smaller] + 1)

 

参考文献

競技プログラミングの鉄則
created by Rinker

コメント

タイトルとURLをコピーしました