Offline Dynamic Connectivity
(DataStructure/UnionFind/OfflineDynamicConnectivity.py)

• View this file on GitHub
• Last update: 2021-01-04 02:54:49+09:00

概要

無向グラフに対して、辺の追加や削除がある場合の連結判定をオフラインで実行する。

使い方

OfflineDynamicConnectivity(q: int, questions: Sequence[Tuple[int, int, int]], n: int)
$n$ 頂点の辺のない無向グラフを初期構築する。予め $q$ 個のクエリを与えておく。計算量 $O(n + q)$
$i$ 番目のクエリ questions[i] の意味は次の通りである。

t u v

時刻 $t$ のとき、頂点 $u$ と頂点 $v$ は連結か？

• insert(t: int, u: int, v: int) -> None
  時刻 $t$ において、頂点 $u$ と頂点 $v$ に辺を張るという操作を与える。時刻 $t$ は、最後に insert や merge を行ったときの時刻 $t_{\mathrm{last}}$ よりも大きくすること！ 計算量 $O(1)$

• erase(t: int, u: int, v: int) -> None
  時刻 $t$ において、頂点 $u$ と頂点 $v$ の辺を削除するという操作を与える。時刻 $t$ は、最後に insert や merge を行ったときの時刻 $t_{\mathrm{last}}$ よりも大きくすること！ 計算量 $O(1)$

• construct() -> int
  与えられた insert と erase の操作をセグメント木上に構築する。insert と erase を行った回数を $r$ 回とすると、計算量 $O(r \log q)$

• run() -> List[bool]
construct したクエリを実行し、その結果を返す。計算量 $O(q + r\log q\log n)$

Depends on

• 巻き戻し可能 Union Find (DataStructure/UnionFind/UnionFindUndo.py)

Verified with

• TestCase/AOJ/2235.test.py

Code

from DataStructure.UnionFind.UnionFindUndo import UnionFindUndo


class OfflineDynamicConnectivity:
    def __init__(self, q, questions, n):
        self.q = q
        self.questions = questions
        self.n = n
        self.add_time = {}
        self.exist = {}
        self.pend = []

        self.size = 2 ** ((q - 1).bit_length())
        self.node = [[] for _ in range(2 * self.size)]
        self.uf = UnionFindUndo(n)

    def insert(self, t, u, v):
        """insert (u, v) edge at time t"""
        if u > v:
            u, v = v, u
        uv = u * self.n + v
        self.add_time[uv] = t
        self.exist[uv] = True

    def erase(self, t, u, v):
        """erase (u, v) edge at time t"""
        if u > v:
            u, v = v, u
        uv = u * self.n + v
        self.exist[uv] = False
        self.pend.append((self.add_time[uv], t, uv))

    def construct(self):
        """construct query on Segment Tree"""
        for uv in self.exist:
            if self.exist[uv]:
                self.pend.append((self.add_time[uv], self.q, uv))
        for l, r, uv in self.pend:
            self._add(l, r, uv)

    def run(self):
        """run queries and get results"""
        self.res = []
        self._dfs()
        return self.res

    def _add(self, l, r, uv):
        """add (u, v) edge in [l, r) of Segment Tree"""
        l, r = l + self.size, r + self.size
        while l < r:
            if l & 1:
                self.node[l].append(uv)
                l += 1
            if r & 1:
                r -= 1
                self.node[r].append(uv)
            l, r = l >> 1, r >> 1

    def _dfs(self, k=1):
        """DFS on Segment Tree"""
        if k >= self.size + self.q:
            return
        for uv in self.node[k]:  # pre-process
            u, v = divmod(uv, self.n)
            self.uf.merge(u, v)

        if k >= self.size:
            self.res.append(self.uf.same(*self.questions[k - self.size]))
        else:
            self._dfs(2 * k)
            self._dfs(2 * k + 1)

        for _ in range(len(self.node[k])):  # post-process
            self.uf.undo()

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