Monoid 作用付き Union Find
(Union_Find/Union_Find_Action.py)

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

Outline

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

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

Theory

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

Contents

$M$ における演算の計算量を $O(f)$ Times とする.

---

Constructer

U = Union_Find_Action(N, op, unit)

• $N$ 頂点の $M$ の元がラベルとして付いている無向 Graph を生成する.
• 制約
  • $\operatorname{op}: M \times M \to M$: Monoid $M$ の演算
  • $\mathrm{unit} \in M$: Monoid $M$ の単位元
• 計算量 : $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$
• 計算量 : Amortized $O(f (\log N)^2)$ 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 M$
• 計算量 : $O(1)$ Time.

---

get

U.get(x)

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

Code

from typing import TypeVar, Generic, Callable

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

        # Monoid に関する値
        self.__op = op
        self.__unit = unit

        # Monoid の積に関する変数
        self.__segments = [[[]] for _ in range(N)]
        self.__provisional = [unit for _ in range(N)]
        self.__time_offset = [0] * N

    def find(self, x: int) -> int:
        return self.__belong[x]

    def union(self, x: int, y: int) -> bool:
        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: M):
        """ x が属する連結成分全てに a を作用させる.

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

        x = self.find(x)
        segment = self.__segments[x]
        op = self.__op

        i = 0
        segment[0].append(a)
        while True:
            if len(segment[i]) % 2 == 1:
                break

            if len(segment[i]) == 2:
                segment.append([])

            i += 1
            segment[i].append(op(segment[i - 1][-1], segment[i - 1][-2]))

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

        Args:
            x (int): 頂点番号
            a (M): 変更後のラベル
        """
        self.__time_offset[x] = len(self.__segments[self.find(x)][0])
        self.__provisional[x] = a

    def get(self, x: int) -> M:
        root = self.find(x)
        lazy = self.__product(self.__segments[root], self.__time_offset[x])
        return self.__op(lazy, self.__provisional[x])

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

    def __product(self, segment: list[list[M]], t: int):
        vl = self.__unit
        vr = self.__unit

        l = t; r = len(segment[0])
        op = self.__op
        for seg in segment:
            if not l < r:
                break

            if l & 1:
                vl = op(seg[l], vl)
                l += 1

            if r & 1:
                r -= 1
                vr = op(vr, seg[r])

            l >>= 1
            r >>= 1

        return op(vr, vl)

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