ポテンシャル付き Union Find
(DataStructure/UnionFind/UnionFindWithPotential.py)

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

概要

素集合を管理するデータ構造。同じ素集合に属する $2$ つの要素間のポテンシャルも同時に管理する。

使い方

UnionFindWithPotential(n: int)
$x = 0, 1, 2, \dots, n - 1$ に対して要素 $x$ の代表元が $x$ となるように、$n$ 個の素集合を構築する。各要素間のポテンシャルは未定義 (つまり INF) とする。計算量 $O(n)$

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

• merge(x: int, y: int, potential: int) -> bool
  要素 $x$ を含む集合と要素 $y$ を含む集合を併合する。要素 $x$ のポテンシャルは要素 $y$ よりも potential ほど高い。併合に成功した場合は True を、失敗した場合（既に併合済みだった場合）は False を返す。計算量 $\mathrm{amortized}\ O(\alpha (n))$

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

• diff(x: int, y: int) -> int
  要素 $x$ と要素 $y$ のポテンシャル差を返す。ポテンシャルが未定義 (つまり要素 $x$ と要素 $y$ が同じ集合に属していない場合) は INF を返す。$\mathrm{amortized}\ O(\alpha (n))$

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

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

Verified with

• TestCase/AOJ/DSL_1_B.test.py

Code

class UnionFindWithPotential:
    def __init__(self, n):
        self.parent = [-1] * n
        self.pot = [0] * n
        self.cnt = n
        self.INF = 10 ** 18

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

    def merge(self, x, y, potential):
        """merge x and y in pot[x] = pot[y] + potential"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return False
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
            self.pot[root_y] = -potential + self.pot[x] - self.pot[y]
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
            self.pot[root_x] = potential - self.pot[x] + self.pot[y]
        self.cnt -= 1
        return True

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

    def diff(self, x, y):
        """get x's potential on a reference point y"""
        if not self.same(x, y):
            # potential is not defined between x and y
            return self.INF
        return self.pot[x] - self.pot[y]

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

    def count(self):
        return self.cnt

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