部分永続 Union Find
(DataStructure/UnionFind/PartiallyPersistentUnionFind.py)

• View this file on GitHub
• Last update: 2021-01-10 07:28:54+09:00

概要

素集合を管理するデータ構造。過去の状態における same と size の操作をサポートする。

使い方

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

• root(t: int, x: int) -> int
  時刻 $t$ における、要素 $x$ の代表元を返す。計算量 $O(\log n)$

• merge(t: int, x: int, y: int) -> bool
  時刻 $t$ において、要素 $x$ を含む集合と要素 $y$ を含む集合を併合する。時刻 $t$ は、最後に merge を行ったときの時刻 $t_{\mathrm{last}}$ よりも大きくすること！ 併合に成功した場合は True を、失敗した場合（既に併合済みだった場合）は False を返す。計算量 $O(\log n)$

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

• size(t: int, x: int) -> int
  時刻 $t$ における、要素 $x$ を含む集合の大きさを返す。計算量 $O(\log n)$

Verified with

• TestCase/yukicoder/yuki0416.test.py

Code

from bisect import bisect_left


class PartiallyPersistentUnionFind:
    def __init__(self, n):
        self.INF = 10 ** 9
        self.parent = [-1] * n
        self.time = [self.INF] * n
        self.size = [[(-1, -1)] for i in range(n)]

    def root(self, t, x):
        while self.time[x] <= t:
            x = self.parent[x]
        return x

    def merge(self, t, x, y):
        x = self.root(t, x)
        y = self.root(t, y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.size[x].append((t, self.parent[x]))
        self.parent[y] = x
        self.time[y] = t
        return True

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

    def size(self, t, x):
        x = self.root(t, x)
        idx = bisect_left(self.size[x], (t, self.INF)) - 1
        return -self.size[x][idx][1]

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