ポテンシャル付き Union Find
(Union_Find/Potentialized_Union_Find.py)

• View this file on GitHub
• Last update: 2025-03-09 00:02:16+09:00

Outline

Union Find にポテンシャルの概念を付け加え, ポテンシャルの差を取得する.

Theory

$G=(G,+,0)$ を可換群とする. $V:=\{0,1,\dots, N-1\}$ として, 写像 $U: V \to G$ には $M$ 個の関係式が以下の形で与えられている.

\[U(y_j)-U(x_j)=u_j \quad (x_j, y_j \in V, u_j \in G \quad (1 \leq j \leq M))\]

Contents

---

Constructer

U=Union_Find(N)

• $N$ 頂点の空グラフを生成する.
• 計算量 : $O(N)$ Time.

---

find

U.find(x)

• $x$ が属する連結成分の代表元を返す.
• 制約
  • $0 \leq x \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time.

---

union

U.union(x,y)

• 無向辺 $xy$ を追加する (この追加によって単純グラフにならなくてもよい).
• 制約
  • $0 \leq x \lt N$
  • $0 \leq y \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time

---

size

U.size(x)

• $x$ が属する連結成分の頂点数を求める.
• 制約
  • $0 \leq x \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time.

---

same

U.same(x,y)

• 2頂点 $x,y$ が連結かどうかを判定する.
• 制約
  • $0 \leq x \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time.

---

members

U.members(x)

• 頂点 $x$ が属する連結成分のリストを求める.
• 制約
  • $0 \leq x \lt N$
• 計算量 : $O(N)$ Time.

---

edge_count

U.edge_count(x)

• 頂点 $x$ が属する連結成分にある辺の数を求める.
• 制約
  • $0 \leq x \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time.

---

is_tree

U.is_tree()

• 頂点 $x$ が属する連結成分が木かどうかを判定する.
• 制約
  • $0 \leq x \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time.

---

tree_count

U.tree_count()

• 木になっている連結成分の数を求める.
• 計算量 : $O(N)$ Time.

---

representive

U.representative()

• 代表元のリストを返す.
• 計算量 : Amortized $O(N)$ Time.

---

group_count

U.group_count()

• 連結成分の数を求める.
• 計算量 : $O(1)$ Time.

---

all_group_members

U.all_group_members()

• 連結成分ごとに分割した dict を返す.
• 計算量 : $O(N)$ Time.

---

group_list

U.group_list(x,y)

• 各頂点が属している連結成分の代表元を返す.
• 計算量 : $O(N)$ Time.

---

refresh

U.refresh()

• 現時点での情報を整理し, データ構造を単純化する.
• 計算量 : $O(N)$ Time.

---

getitem

U[x]

• U.find(x) と同等.
• 制約
  • $0 \leq x \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time.

---

setitem

U[x]=y

• U.union(x,y) と同等
• 制約
  • $0 \leq x \lt N$
• 計算量 : Amortized $O(\alpha(N))$ Time.

Code

from typing import TypeVar, Generic, Callable

G = TypeVar('G')
class Potentilized_Union_Find(Generic[G]):
    def __init__(self, N: int, op: Callable[[G, G], G], zero: G, neg: Callable[[G], G]):
        """ 0, 1, ..., N - 1 を要素としたポテンシャル付き Union_Find を実装する.

        Args:
            N (int): 要素数
            op (Callable[[G, G], G]): 群演算
            zero (G): 群 G 上の単位元
            neg (Callable[[G], G]): 群 G の逆元を求める関数
        """

        self.n = N
        self.parents = [-1] * N
        self.rank = [0] * N
        self.edges = [0] * N
        self.pot = [zero] * N
        self.valid = [True] * N
        self.__group_number = N

        self.op = op
        self.diff : Callable[[G, G], G] = lambda u, v: self.op(u, self.neg(v)) # diff(u, v) = U(u) - U(v)
        self.zero = zero
        self.neg = neg

    def find(self, x: int) -> int:
        """ 要素 x が属している族を調べる

        Args:
            x (int): 要素

        Returns:
            int: x が属している族
        """

        if self.parents[x]<0:
            return x

        par=self.parents; pot=self.pot; op=self.op

        r=x
        data=[]
        while par[r]>=0:
            data.append(r)
            r=par[r]

        for x in data[::-1]:
            pot[x]=self.op(pot[x], pot[par[x]])
            par[x]=r

        return r

    def union(self, x: int, y: int, u: G) -> None:
        """ 要素 x, y を同一視し, U(y) - U(x) = u という情報を加える.

        Args:
            x (int): 基準点
            y (int): 対象点
            u (G): ポテンシャルの差
        """

        a=self.find(x); b=self.find(y)
        u=self.op(u, self.diff(self.pot[x],self.pot[y]))
        x=a; y=b

        if x==y:
            self.valid[x]&=self.diff(self.pot[y],self.pot[x])==u
            self.edges[x]+=1
            return

        if self.rank[x]<self.rank[y]:
            x,y=y,x
            u=self.neg(u)
        elif self.rank[x]==self.rank[y]:
            self.rank[x]+=1

        self.parents[x]+=self.parents[y]
        self.parents[y]=x

        self.edges[x]+=self.edges[y]+1
        self.edges[y]=0

        self.valid[x]&=self.valid[y]

        self.pot[y]=u

        self.__group_number-=1

        return

    def size(self, x: int) -> int:
        """ 要素 x が属している族のサイズを求める

        Args:
            x (int): 要素

        Returns:
            int: 要素 x が属している族のサイズ
        """

        return -self.parents[self.find(x)]

    def potential_energy(self, x: int, y: int) -> G | None:
        """ x を基準にした y のポテンシャルエネルギー

        Args:
            x (int): 基準点
            y (int): ポテンシャルを求める点

        Returns:
            G | None: 不明な場合や非妥当である場合は None
        """

        if self.same(x,y) and self.is_valid(x):
            return self.diff(self.pot[y], self.pot[x])
        else:
            return None

    def same(self, x: int, y: int) -> bool:
        """ 要素 x, y は同一視されているか?

        Args:
            x (int): 要素
            y (int): 要素

        Returns:
            bool: x, y が同一視されていれば True, そうでなければ False
        """

        return self.find(x) == self.find(y)

    def is_possible(self, x: int, y: int, a: G) -> bool:
        """ U(y) - U(x) = a となり得るか?
        (x, y の属する族のポテンシャルが矛盾していたら確定 False)

        Args:
            x (int):
            y (int):
            a (G):

        Returns:
            bool: なり得るならば True, そうでなければ False
        """

        if not(self.is_valid(x) and self.is_valid(y)):
            return False

        if not self.same(x, y):
            return True

        return self.diff(self.pot[y], self.pot[x]) == a

    def members(self, x: int) -> list[int]:
        """ 要素 x と同一視されている要素のリスト

        Args:
            x (int): 要素

        Returns:
            list[int]: 要素 x と同一視されている要素のリスト
        """

        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def edge_count(self, x: int) -> int:
        """ 要素 x が属している族における辺の数を求める.

        Args:
            x (int): 要素

        Returns:
            int: 要素 x が属している族における辺の数を求める
        """

        return self.edges[self.find(x)]

    def is_valid(self, x: int) -> bool:
        """ x が属している族のポテンシャルが妥当かどうかを判定する.

        Args:
            x (int): 点

        Returns:
            bool: 妥当ならば True, そうでなければ False
        """

        return self.valid[self.find(x)]

    def is_well_defined(self) -> bool:
        """ この系全体のポテンシャルが妥当かどうかを判定する.

        Returns:
            bool: 妥当ならば True, そうでなければ False
        """

        return all(self.is_valid(x) for x in range(self.n))

    def is_tree(self, x):
        """ 要素 x が属する族が森かどうかを判定する.

        x: 要素
        """
        return self.size(x)==self.edges[self.find(x)]+1

    def tree_count(self) -> int:
        """ 木になっている族の数を計上する

        Returns:
            int: 木になっている族の数
        """

        return sum(self.is_tree(g) for g in self.representative())

    def representative(self) -> list[int]:
        """ 代表元のリストを出力する

        Returns:
            list[int]: 代表元のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self) -> int:
        """ 族の個数を出力する.

        Returns:
            int: 族の個数
        """

        return self.__group_number

    def all_group_members(self) -> dict[int, list[int]]:
        """ 全ての族の出力
        """

        groups: dict[int, list[int]] = { r: [] for r in self.representative() }
        for x in range(self.n):
            groups[self.find(x)].append(x)
        return groups

    def group_list(self) -> list[int]:
        """ 各要素について, その要素が属する族の代表元からなるリストを求める.

        Returns:
            list[int]: 第 x 要素は x が属する族の代表元.
        """

        return [self.find(x) for x in range(self.n)]

    def refresh(self):
        """ Union Find の情報を簡潔にする.
        """

        for i in range(self.n):
            self.find(i)

    def __str__(self):
        return ', '.join(f'{r}: {self.members(r)}' for r in self.representative())

    def __repr__(self):
        return f"{self.__class__.__name__}({self.n}, {self.op}, {self.zero}, {self.neg})"

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

Back to top page