問題
$N$ 頂点グラフに $Q$ クエリ:
add u v— 辺を追加del u v— 辺を削除（存在保証）query u v— 連結か答える（Yes/No）
制約
$1 \le N \le 3 \times 10^5$
$1 \le Q \le 3 \times 10^5$
多重辺あり可能
入出力例
入力例 1
4 6
add 1 2
add 2 3
query 1 3
del 2 3
query 1 3
query 3 4出力例 1
Yes
No
Noヒント (段階的開示)
ヒント1: 方向性
オフライン処理なら「Offline Dynamic Connectivity (分割統治 + Undo DSU)」で $O(Q \log Q \cdot \alpha(N))$ で解ける。
ヒント2: アプローチ
各辺を「存在する時間区間 $[l, r)$」に変換。時間軸セグメント木の各ノードに辺を登録。DFS 中に Union/Undo を行う。
ヒント3: 誘導
Path Compression を使わず Union by Rank のみ。変更を履歴に push し、再帰の戻りで pop & 復元。
模範解答 (Python)
import sys
from collections import defaultdict
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
queries = []
for _ in range(Q):
parts = input().split()
t, u, v = parts[0], int(parts[1]), int(parts[2])
u -= 1; v -= 1
if u > v:
u, v = v, u
queries.append((t, u, v))
edge_last_add = {}
edge_intervals = defaultdict(list)
for i, (t, u, v) in enumerate(queries):
key = (u, v)
if t == 'add':
edge_last_add.setdefault(key, []).append(i)
elif t == 'del':
l = edge_last_add[key].pop()
edge_intervals[key].append((l, i))
for key, stack in edge_last_add.items():
for l in stack:
edge_intervals[key].append((l, Q))
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((y, self.parent[y], x, self.rank[x]))
self.parent[y] = x
if self.rank[x] == self.rank[y]:
self.rank[x] += 1
def undo(self):
op = self.history.pop()
if op is None:
return
y, old_parent_y, x, old_rank_x = op
self.parent[y] = old_parent_y
self.rank[x] = old_rank_x
def connected(self, x, y):
return self.find(x) == self.find(y)
seg_size = 1
while seg_size < Q:
seg_size <<= 1
seg = [[] for _ in range(2 * seg_size)]
def seg_add(l, r, val, node=1, lo=0, hi=None):
if hi is None:
hi = seg_size
if r <= lo or hi <= l:
return
if l <= lo and hi <= r:
seg[node].append(val)
return
mid = (lo + hi) // 2
seg_add(l, r, val, 2*node, lo, mid)
seg_add(l, r, val, 2*node+1, mid, hi)
for key, intervals in edge_intervals.items():
u, v = key
for l, r in intervals:
seg_add(l, r, (u, v))
dsu = UndoDSU(N)
results = []
def dfs(node, lo, hi):
edges_added = len(seg[node])
for u, v in seg[node]:
dsu.union(u, v)
if hi - lo == 1:
if lo < Q:
t, u, v = queries[lo]
if t == 'query':
results.append('Yes' if dsu.connected(u, v) else 'No')
else:
mid = (lo + hi) // 2
dfs(2*node, lo, mid)
dfs(2*node+1, mid, hi)
for _ in range(edges_added):
dsu.undo()
sys.setrecursionlimit(1000000)
dfs(1, 0, seg_size)
print('\n'.join(results))
solve()Step-by-Step 解説
1辺の時間区間化
各辺 $(u,v)$ を「存在する時間区間 $[l, r)$」に変換。最後まで削除されない辺は $[l, Q)$。
各辺 $(u,v)$ を「存在する時間区間 $[l, r)$」に変換。最後まで削除されない辺は $[l, Q)$。
2Undo 可能 DSU
Path Compression を使わず Union by Rank のみ。変更操作をスタックに記録し、Undo で逆順復元。高さ $O(\log N)$。
Path Compression を使わず Union by Rank のみ。変更操作をスタックに記録し、Undo で逆順復元。高さ $O(\log N)$。
3セグ木に辺登録
各区間 $[l, r)$ をセグ木の $O(\log Q)$ ノードに分割して格納。
各区間 $[l, r)$ をセグ木の $O(\log Q)$ ノードに分割して格納。
4DFS で Union/Undo
ノード入 → 辺を Union、葉でクエリ処理、ノード出 → Undo。計算量 $O(Q \log Q \cdot \log N)$。
ノード入 → 辺を Union、葉でクエリ処理、ノード出 → Undo。計算量 $O(Q \log Q \cdot \log N)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| Path Compression を使う | Undo 不可能になる | Union by Rank のみ |
| Undo 回数を間違える | 辺数を忘れる | edges_added = len(seg[node]) |
| 多重辺の処理 | 同辺の複数追加 | edge_last_add[key] をリスト管理 |
次のステップ
- 辺の重みあり + 連結成分の最小辺重み
- Link-Cut Tree によるオンライン版
- ETT との比較