UnionFind
(lib/data_structure/union_find.py)

• View this file on GitHub
• Last update: 2022-06-26 23:15:33+09:00

Union-Find Tree (Disjoint Set Union)

データの集合を素集合に分割してもつデータ構造

以下の二つの操作をともに $O(\alpha(N))$ で行える（$\alpha(N)$ はアッカーマン関数 $A(N, N)$ の逆関数）

• union: 2つの集合をマージする
• find: ある要素がどの集合に含まれるかを求める

Implementations

def __init__(self, n: int)

サイズ $n$ の UnionFind を生成する
$O(N)$

---

def union(self, x: int, y: int) -> bool

x と y をマージする
マージに成功した場合 True 、失敗した場合 False を返す
amortized $O(\alpha(N))$

---

def find(self, x: int) -> int

x を含む連結成分の根を返す
amortized $O(\alpha(N))$

---

def same(self, x: int, y: int) -> bool

x と y が同じ連結成分に含まれているかを返す
amortized $O(\alpha(N))$

---

Verified with

• verify/data_structure/union_find.test.py

Code

class UnionFind:
    def __init__(self, n: int):
        self._n = n
        self._parents = [-1] * n

    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        else:
            self._parents[x] = self.find(self._parents[x])
            return self._parents[x]

    def union(self, x: int, y: int) -> bool:
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False

        if self._parents[x] > self._parents[y]:
            x, y = y, x

        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page