Day 055-Q2 — Offline Dynamic Connectivity

2026-06-08 赤色 Master / Phase 8+ ★★★★★★★★★ 辺削除分割統治 / Undo DSU / セグメント木

問題

$N$ 頂点のグラフに $Q$ 個のクエリが与えられる。各クエリは:

  • 1 u v: 辺 $(u, v)$ を追加
  • 2 u v: 辺 $(u, v)$ を削除（必ず存在する）
  • 3 u v: 頂点 $u, v$ が連結かどうか答える

辺の追加・削除を含む動的グラフの連結性クエリをオフラインで処理せよ。

制約

パラメータ範囲
$N$$2 \le N \le 10^5$
$Q$$1 \le Q \le 2 \times 10^5$
辺の存在保証削除クエリは必ず現在グラフに存在する辺に対して行う

入出力例

入力例 1

4 7
1 1 2
1 2 3
3 1 3
2 1 2
3 1 3
1 1 4
3 1 4

出力例 1

Yes
No
Yes

概念図: 時刻軸セグメント木 + Undo DSU

辺 (1,2) の存在区間 [0,3) をセグメント木に登録する例（Q=7） 時刻軸: → 時刻 0 1 2 3 4 5 6 add(1,2) add(2,3) ? 1-3 del(1,2) ? 1-3 add(1,4) ? 1-4 辺 (1,2): [0, 3) 辺 (2,3): [1, 7) 辺 (1,4): [5, 7) セグメント木（時刻軸）への辺登録: [0, 8) [0, 4) [4, 8) [0, 2) [2, 4) ← (1,2)がここに登録 ↑ (2,3)がここに

ヒント（段階的開示）

ヒント1: 方向性
各辺の「存在する時間区間 $[t_{add}, t_{del})$」を求め、時刻軸のセグメント木の各ノードに辺を割り当てる。セグメント木を DFS しながら Undo 可能な DSU（Union by rank、パス圧縮なし）で union/undo を行う。計算量 $O(Q \log^2 Q)$。
ヒント2: アプローチ
  1. 各辺の (追加時刻, 削除時刻) を求める（存在区間）
  2. セグメント木（時刻軸 $[0, Q)$）の各ノードに区間をカバーするように辺を追加（$O(\log Q)$ ノード）
  3. セグメント木を DFS。ノードに入るとき辺を union（Undo DSU）、抜けるとき rollback
  4. 葉ノードに対応する時刻がクエリ3なら、連結性を判定して出力
ヒント3: コード骨格 
# Undo DSU: Union by rank, NO path compression
class UndoDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.history = []

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

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

    def rollback(self):
        op = self.history.pop()
        if op is None: return
        x, y, rk = op
        self.parent[y] = y; self.rank[x] = rk

# DFS on segment tree
def dfs(node, l, r):
    for u, v in seg[node]: dsu.union(u, v)
    if r - l == 1:
        if queries[l][0] == 3: # answer query
            ...
    else:
        mid = (l + r) // 2
        dfs(2*node, l, mid); dfs(2*node+1, mid, r)
    for _ in seg[node]: dsu.rollback()

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    queries = []
    for i in range(Q):
        queries.append(list(map(int, input().split())))

    edge_intervals = []
    active = defaultdict(list)

    for t, q in enumerate(queries):
        if q[0] == 1:
            e = (min(q[1], q[2]), max(q[1], q[2]))
            active[e].append(t)
        elif q[0] == 2:
            e = (min(q[1], q[2]), max(q[1], q[2]))
            add_t = active[e].pop()
            edge_intervals.append((e[0]-1, e[1]-1, add_t, t))
    for e, times in active.items():
        for add_t in times:
            edge_intervals.append((e[0]-1, e[1]-1, add_t, Q))

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

    def seg_add(l, r, val):
        l += SIZE; r += SIZE
        while l < r:
            if l & 1: seg[l].append(val); l += 1
            if r & 1: r -= 1; seg[r].append(val)
            l >>= 1; r >>= 1

    for u, v, l, r in edge_intervals:
        if l < r: seg_add(l, r, (u, v))

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

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

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

    def rollback():
        op = history.pop()
        if op is None: return
        x, y, rk = op
        parent[y] = y; rank[x] = rk

    answers = []

    def dfs(node, l, r):
        for u, v in seg[node]: union(u, v)
        if r - l == 1:
            if l < Q and queries[l][0] == 3:
                u, v = queries[l][1]-1, queries[l][2]-1
                answers.append((l, "Yes" if find(u) == find(v) else "No"))
        else:
            mid = (l + r) // 2
            dfs(2*node, l, mid); dfs(2*node+1, mid, r)
        for _ in seg[node]: rollback()

    sys.setrecursionlimit(600000)
    dfs(1, 0, SIZE)
    answers.sort()
    sys.stdout.write('\n'.join(a for _, a in answers) + '\n')

solve()

Step-by-Step 解説

1辺の存在区間の計算
各辺の追加クエリ時刻と削除クエリ時刻を記録。辺の存在区間 $[t_{add}, t_{del})$ を求める。削除されなかった辺は $[t_{add}, Q)$。
2セグメント木への辺の登録
時刻軸 $[0, Q)$ のセグメント木（2倍展開、配列ベース）。辺の存在区間を $O(\log Q)$ 個のノードに分解して登録（通常のセグメント木の区間更新と同じ手順）。
3DFS + Undo DSU
セグメント木を DFS。ノードに入るとき全辺を union。葉でクエリ3に回答。ノードを抜けるとき同数の rollback。rollback は history スタックで管理。
4Undo DSU の正確性
Path compression を使わず Union by rank のみ。find が $O(\log N)$ になるが、rollback が可能。全体の計算量は $O(Q \log^2 Q)$。

計算量

辺区間計算: $O(Q)$
セグメント木登録: $O(Q \log Q)$（各辺を $O(\log Q)$ ノードに登録）
DFS + DSU: $O(Q \log Q \cdot \log N)$ = $O(Q \log^2 Q)$（$N \le Q$ の場合）
全体: $O(Q \log^2 Q)$

よくあるミス

ミス原因正しい書き方
Path compression を使用undo が不可能になるUnion by rank のみ（compress なし）
rollback 回数の不一致union で変化なしでも history に push が必要union 変化なしのとき history.append(None)
セグメント木のサイズ不足SIZE < Q の場合while SIZE < Q: SIZE <<= 1
再帰深さ超過セグメント木 DFS の最大深さが $\log Q \approx 18$sys.setrecursionlimit(600000)

次のステップ

  • 発展問題: 辺の追加・削除 + 連結成分のサイズ最大値クエリ（DSU に size を持たせる）
  • 関連: オンライン動的連結性（Link-Cut Tree で解くアプローチとの比較）
  • 応用: オフライン動的最小全域木（辺削除後の MST 維持）

自己評価