巻き戻し可能 Union Find
(DataStructure/UnionFind/UnionFindUndo.py)

• View this file on GitHub
• Last update: 2021-01-03 22:00:08+09:00

概要

素集合を管理するデータ構造。集合の併合操作を巻き戻すことができる。

使い方

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

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

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

• undo() -> None
  直前に実行した merge 操作を $1$ 回分巻き戻す。計算量 $O(1)$

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

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

Required by

• Offline Dynamic Connectivity (DataStructure/UnionFind/OfflineDynamicConnectivity.py)

Verified with

• TestCase/LibraryChecker/persistent_unionfind.Undo.test.py

Code

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

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

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        self.history.append((x, self.parent[x]))
        self.history.append((y, self.parent[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
        return True

    def undo(self):
        if not self.history:
            return False
        for _ in range(2):
            x, par_x = self.history.pop()
            self.parent[x] = par_x
        return True

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

    def size(self, x):
        return -self.parent[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