Day 033-Q3 | オフライン動的グラフ連結性

問題

$N$ 頂点のグラフに対して $Q$ 個のクエリを処理。add u v / del u v / query u v の3種類。

入力形式

N Q
query_1
...
query_Q

制約

$2 \le N \le 10^5$

$1 \le Q \le 2 \times 10^5$

同時存在辺数 $\le 10^5$

del は事前 add 済み辺のみ

入出力例

入力例 1

4 7
add 1 2
add 2 3
query 1 3
del 1 2
query 1 3
add 1 4
query 1 3

出力例 1

Yes
Yes
No

ヒント (段階的開示)

ヒント1: 方向性

オフラインなら分割統治 + Undo DSU。各辺の存在区間をセグメント木に貼る。

ヒント2: アプローチ

辺 $(u,v)$ の存在期間 $[l, r)$ を時間軸セグメント木の $O(\log Q)$ ノードに登録。DFS で各葉の連結性を判定。

ヒント3: 誘導

Undo DSU は union by rank のみで経路圧縮なし。各 union を履歴スタックに記録し、葉から戻る際に undo。

模範解答 (Python)

import sys
from collections import defaultdict

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx+1]); idx += 2

    queries = []
    for i in range(Q):
        t = data[idx]; idx += 1
        u, v = int(data[idx]), int(data[idx+1]); idx += 2
        if u > v:
            u, v = v, u
        queries.append((t, u, v))

    parent = list(range(N + 1))
    rank = [0] * (N + 1)
    history = []

    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            history.append(None)
            return
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        history.append((rx, ry, rank[rx]))
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1

    def undo():
        op = history.pop()
        if op is None:
            return
        rx, ry, old_rank = op
        parent[ry] = ry
        rank[rx] = old_rank

    def connected(x, y):
        return find(x) == find(y)

    seg_size = 1
    while seg_size < Q:
        seg_size <<= 1
    seg = [[] for _ in range(2 * seg_size)]

    def seg_add(l, r, edge, node=1, nl=0, nr=None):
        if nr is None:
            nr = seg_size
        if r <= nl or nr <= l:
            return
        if l <= nl and nr <= r:
            seg[node].append(edge)
            return
        mid = (nl + nr) // 2
        seg_add(l, r, edge, 2*node, nl, mid)
        seg_add(l, r, edge, 2*node+1, mid, nr)

    active = {}
    query_map = {}

    for i, (t, u, v) in enumerate(queries):
        if t == 'add':
            active[(u, v)] = i
        elif t == 'del':
            start = active.pop((u, v))
            seg_add(start, i, (u, v))
        else:
            query_map[i] = (u, v)

    for (u, v), start in active.items():
        seg_add(start, Q, (u, v))

    results = []

    def dfs(node, nl, nr):
        cnt = 0
        for u, v in seg[node]:
            union(u, v)
            cnt += 1

        if nr - nl == 1:
            if nl < Q and nl in query_map:
                u, v = query_map[nl]
                results.append('Yes' if connected(u, v) else 'No')
        else:
            mid = (nl + nr) // 2
            dfs(2*node, nl, mid)
            dfs(2*node+1, mid, nr)

        for _ in range(cnt):
            undo()

    sys.setrecursionlimit(10**6)
    dfs(1, 0, seg_size)

    sys.stdout.write('\n'.join(results) + '\n')

solve()

Step-by-Step 解説

1辺の存在期間を特定
add 時の $i$ と del 時の $j$ で $[i, j)$。削除なしは $[i, Q)$。

2セグメント木に辺を貼る
時間軸 $[0, Q)$ のセグメント木の $O(\log Q)$ ノードに辺を追加。

3Undo DSU
union by rank のみ。経路圧縮なし。各 union を履歴に記録。undo() は $O(1)$。

4DFS で連結性判定
各ノード進入時に辺を union、退出時に undo。葉が query ならその時点の連結性を答える。

計算量

辺貼り付け: $O(\log Q)$/辺
各 union: $O(\log N)$
全体: $O(Q \log^2 N)$

よくあるミス

ミス	原因	正しい書き方
経路圧縮 DSU で undo	圧縮は巻き戻せない	union by rank のみ
`del` で辺不在	`active` 管理ミス	`add` 時に必ず登録
(u,v)/(v,u) 別扱い	無向辺を有向で管理	`if u>v: u,v=v,u` 正規化
再帰深度超過	Python のデフォルト制限	`sys.setrecursionlimit(10**6)`

Day 033-Q3 — オフライン動的グラフ連結性（Offline Dynamic Connectivity + Undo DSU）

問題