群作用付き Union Find
(Union_Find/Union_Find_Group_Action.py)

• View this file on GitHub
• Last update: 2025-03-29 15:18:46+09:00

Outline

各頂点に群 $G$ の元がラベルとして付いている無向 Graph 上 $H = (V, E)$ に対して, 以下の処理を高速に行う.

• union(x, y): 頂点 $x$ と頂点 $y$ を結ぶ辺を追加する.
• find(x): 頂点 $x$ が属する連結成分の代表元を求める.
• same(x, y): 頂点 $x$ と頂点 $y$ は連結か?
• action(x, a): 頂点 $x$ が属する連結成分上の頂点全てに対して, $a \in G$ を作用させる。.
• update(x, a): 頂点 $x$ を $a \in G$ に更新する.
• get(x): 頂点 $x$ のラベルを求める.

Theory

$H = (V,E)$ を無向 Graph とし, $G$ を群とする.

Contents

$G$ における演算, 逆元計算の計算量を $O(f)$ Times とする.

---

Constructer

U = Union_Find_Action(N, op, unit, inv)

• $N$ 頂点の $G$ の元がラベルとして付いている無向 Graph を生成する.
• 制約
  • $\operatorname{op}: G \times G \to G; (x, y) \mapsto xy$: 群 $G$ の演算
  • $\mathrm{unit} \in G$: 群 $G$ の単位元
  • $\mathrm{inv}: G \to G; x \mapsto x^{-1}$: 群 $G$ の逆元関数
• 計算量 : $O(N)$ Time.

---

find

U.find(x)

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

---

union

U.union(x, y)

• 無向辺 $xy$ を追加する.
• 制約
  • $0 \leq x \lt N$
  • $0 \leq y \lt N$
• 計算量 : $O(f \log N)$ Time

---

size

U.size(x)

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

---

same

U.same(x, y)

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

---

update

U.update(x, a)

• 頂点 $x$ のラベルを $a$ に変更する.
• 制約
  • $0 \leq x \lt N$
  • $a \in G$
• 計算量 : $O(f)$ Time.

---

get

U.get(x)

• 頂点 $x$ におけるラベルを求める.
• 制約
  • $0 \leq x \lt N$
• 計算量 : $O(f)$ Time.

Code

from typing import TypeVar, Generic, Callable

G = TypeVar('G')
class Union_Find_Group_Action(Generic[G]):
    def __init__(self, N: int, op: Callable[[G, G], G], unit: G, inv: Callable[[G], G]):
        # Union Find で用いる変数
        self.__groups = [[x] for x in range(N)]
        self.__belong = [x for x in range(N)]

        # Group に関する値
        self.__op = op
        self.__inv = inv

        # Group の積に関する変数
        self.__lazy = [unit for _ in range(N)]
        self.__provisional = [unit for _ in range(N)]

    def find(self, x: int) -> int:
        """ 頂点 x が属する連結成分の代表元を求める.

        Args:
            x (int): 頂点番号

        Returns:
            int: 頂点 x が属する連結成分の代表元
        """
        return self.__belong[x]

    def union(self, x: int, y: int) -> bool:
        """ 頂点 x と頂点 y を結ぶ辺を追加する.

        Args:
            x (int): 頂点番号
            y (int): 頂点番号

        Returns:
            bool: 元々頂点 x と頂点 y が非連結ならば True, 連結ならば False
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False

        if self.size(x) < self.size(y):
            x, y = y, x

        self.__groups[x].extend(self.__groups[y])
        memo = [self.get(z) for z in self.__groups[y]]
        for z, b in zip(self.__groups[y], memo):
            self.__belong[z] = x
            self.update(z, b)

        self.__groups[y].clear()

        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        return len(self.__groups[self.find(x)])

    def action(self, x: int, a: G):
        """ x が属する連結成分全てに a を作用させる.

        Args:
            x (int): 頂点番号
            a (G): 作用
        """

        x = self.find(x)
        self.__lazy[x] = self.__op(a, self.__lazy[x])

    def update(self, x: int, a: G):
        """ 頂点 x のラベルを a に更新する.

        Args:
            x (int): 頂点番号
            a (G): 変更後のラベル
        """

        self.__provisional[x] = self.__op(self.__inv(self.__lazy[self.find(x)]), a)

    def get(self, x: int) -> G:
        """ 頂点 x のラベルを取得する.

        Args:
            x (int): 頂点番号

        Returns:
            G: 頂点 x のラベル
        """

        return self.__op(self.__lazy[self.find(x)], self.__provisional[x])

    def __getitem__(self, x: int) -> G:
        return self.get(x)

    def __len__(self) -> int:
        return len(self.__belong)

    def __iter__(self):
        yield from [self.get(x) for x in range(len(self))]

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

Back to top page