永続 Union Find
(DataStructure/UnionFind/PersistentUnionFind.py)

• View this file on GitHub
• Last update: 2021-07-18 20:19:20+09:00

概要

永続化された素集合データ構造。つまり、merge 前後のバージョンを常に保持し、全バージョンに対する same、size が可能である。

使い方

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

• root(x: int) -> int
  要素 $x$ の代表元を返す。算量 $O(\log n)$

• merge(x: int, y: int) -> PersistentUnionFind
  要素 $x$ を含む集合と要素 $y$ を含む集合を併合したときの PersistentUnionFind を返す。計算量 $O(\log n)$

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

• size(x: int) -> int
  集合の個数を返す。計算量 $O(\log n)$

Depends on

• 永続配列 (DataStructure/misc/PersistentArray.py)

Verified with

• TestCase/LibraryChecker/persistent_unionfind.test.py

Code

from DataStructure.misc.PersistentArray import (
    PersistentArray,
    init_persistent_array
)


class PersistentUnionFind:
    def __init__(self, n):
        if type(n) is int:
            self.parent = init_persistent_array([-1 for _ in range(n)])
        else:
            self.parent = n

    def root(self, x):
        px = self.parent.get(x)
        if px < 0:
            return x
        return self.root(px)

    def merge(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return self
        px = self.parent.get(x)
        py = self.parent.get(y)
        if px > py:
            x, y = y, x
        tmp = self.parent.set(y, x)
        return PersistentUnionFind(tmp.set(x, px + py))

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

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

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