問題
$N$ 頂点 $M$ 辺の無向グラフに対し、$Q$ 個のクエリ（ADD u v / DEL u v / QUERY u v）を処理せよ。クエリはオフライン処理可（先読み可）。
制約
$1 \le N \le 10^5$
$0 \le M \le 10^5$
$1 \le Q \le 10^5$
DEL は存在する辺のみ
自己ループ・多重辺なし
入出力例
入力例 1
4 1
1 2
6
QUERY 1 2
ADD 2 3
ADD 3 4
QUERY 1 4
DEL 1 2
QUERY 1 4出力例 1
Yes
Yes
Noヒント (段階的開示)
ヒント1: 方向性
各辺の「存在期間 $[l,r)$」をセグメント木の区間に貼り付ける。
ヒント2: アプローチ
セグメント木上を DFS し、ノード訪問時に辺を Undo DSU で union、バックトラックで undo。計算量 $O((Q+M)\log^2 Q)$。
ヒント3: 誘導
Undo DSU は union by rank のみ（パス圧縮なし）。union 操作を history スタックに積み、undo で巻き戻し。
模範解答 (Python)
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(500000)
def solve():
N, M = map(int, input().split())
initial_edges = [tuple(map(int, input().split())) for _ in range(M)]
Q_cnt = int(input())
queries = []
for _ in range(Q_cnt):
parts = input().split()
queries.append((parts[0], int(parts[1]), int(parts[2])))
edge_live = {}
for u, v in initial_edges:
edge_live[(min(u,v), max(u,v))] = 0
seg_size = 1
while seg_size < Q_cnt + 1:
seg_size <<= 1
seg = [[] for _ in range(2 * seg_size)]
def add_to_seg(l, r, edge, 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(edge)
return
mid = (lo + hi) // 2
add_to_seg(l, r, edge, 2*node, lo, mid)
add_to_seg(l, r, edge, 2*node+1, mid, hi)
for i, (typ, u, v) in enumerate(queries):
key = (min(u,v), max(u,v))
if typ == 'ADD':
edge_live[key] = i + 1
elif typ == 'DEL':
start = edge_live.pop(key)
add_to_seg(start, i + 1, key)
for key, start in edge_live.items():
add_to_seg(start, Q_cnt + 1, key)
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, parent[rx], rank[rx], ry, parent[ry], rank[ry]))
parent[ry] = rx
if rank[rx] == rank[ry]:
rank[rx] += 1
def undo():
h = history.pop()
if h is None: return
rx, prx, rrx, ry, pry, rry = h
parent[rx] = prx; rank[rx] = rrx
parent[ry] = pry; rank[ry] = rry
results = []
def dfs(node, lo, hi):
cnt = len(seg[node])
for (u, v) in seg[node]:
union(u, v)
if lo + 1 == hi:
if lo < Q_cnt:
typ, u, v = queries[lo]
if typ == 'QUERY':
results.append('Yes' if find(u) == find(v) else 'No')
else:
mid = (lo + hi) // 2
dfs(2*node, lo, mid)
dfs(2*node+1, mid, hi)
for _ in range(cnt):
undo()
dfs(1, 0, seg_size)
print('\n'.join(results))
solve()Step-by-Step 解説
1各辺の存在区間を計算
ADD で開始、DEL で終了。残った辺は $[start, Q)$。
ADD で開始、DEL で終了。残った辺は $[start, Q)$。
2セグメント木に辺を配置
各辺の区間 $[l,r)$ を $O(\log Q)$ ノードに分散して貼る。
各辺の区間 $[l,r)$ を $O(\log Q)$ ノードに分散して貼る。
3Undo DSU
union by rank のみ、操作履歴をスタックに積む。
union by rank のみ、操作履歴をスタックに積む。
4DFS 走査
ノード訪問で union、葉で QUERY 判定、バックトラックで undo。
ノード訪問で union、葉で QUERY 判定、バックトラックで undo。
5結果出力
DFS 中に集めた QUERY 結果を順番に出力。
DFS 中に集めた QUERY 結果を順番に出力。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| パス圧縮を使う | undo できなくなる | union by rank のみ |
| ADD/DEL の対応ミス | キーが不一致 | (min(u,v), max(u,v)) で正規化 |
| セグメント木サイズ不足 | 末尾辺で範囲外 | seg_size >= Q+1 |
| 再帰上限 | Pythonデフォルト 1000 | sys.setrecursionlimit |
次のステップ
- 辺重み付き Undo Weighted DSU