Union Find
(DataStructure/UnionFind/UnionFind.py)

• View this file on GitHub
• Last update: 2021-01-02 02:09:18+09:00

概要

素集合を管理するデータ構造。

使い方

UnionFind(n: int)
$x = 0, 1, 2, \dots, n - 1$ に対して要素 $x$ の代表元が $x$ となるように、$n$ 個の素集合を構築する。計算量 $O(n)$

• root(x: int) -> int
  要素 $x$ の代表元を返す。計算量 $\mathrm{amortized}\ O(\alpha (n))$

• merge(x: int, y: int) -> bool
  要素 $x$ を含む集合と要素 $y$ を含む集合を併合する。併合に成功した場合は True を、失敗した場合（既に併合済みだった場合）は False を返す。計算量 $\mathrm{amortized}\ O(\alpha (n))$

• same(x: int, y: int) -> bool
  要素 $x$ と要素 $y$ が同じ集合に属するかどうかを返す。計算量 $\mathrm{amortized}\ O(\alpha (n))$

• size(x: int) -> int
  要素 $x$ を含む集合の大きさを返す。計算量 $\mathrm{amortized}\ O(\alpha (n))$

• count() -> int
  集合の個数を返す。計算量 $O(1)$

• groups() -> List[List[int]]
  すべての集合とその要素を列挙する。計算量 $O(n)$

Required by

• 最小全域木 (ブルーフカ法) (Graph/SpanningTree/boruvka.py)
• 最小有向全域木 (Graph/SpanningTree/directed_mst.py)
• 最小全域木 (クラスカル法) (Graph/SpanningTree/kruskal.py)
• 最小共通祖先 (Tarjan のオフラインアルゴリズム) (Graph/Tree/offline_lca.py)
• 有向グラフのオイラー路 (Graph/misc/DirectedEulerian.py)
• 無向グラフのオイラー路 (Graph/misc/UndirectedEulerian.py)

Verified with

• TestCase/AOJ/2821.test.py
• TestCase/AOJ/DSL_1_A.test.py
• TestCase/yukicoder/yuki0922.HLDecomposition.test.py
• TestCase/yukicoder/yuki0922.test.py

Code

class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.n = n
        self.cnt = n

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1
        return True

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parent[self.root(x)]

    def count(self):
        return self.cnt

    def groups(self):
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            res[self.root(i)].append(i)
        return [group for group in res if group]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/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.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page