题干与适用场景
给定 n 个用户和 q 个按时间排列的操作。add id u v 在时间点加入一条带 ID 的无向关系，remove id 删除这条关系，ask u v 查询两人当前是否连通。每条关系最多添加和删除一次，所有操作已知后才开始回答查询。
题目要求输出每个 ask 的布尔结果。需要说明普通并查集为什么无法安全处理删除、如何把关系的存活时间映射到时间线、如何恢复状态，以及边界条件和复杂度。目标是离线动态连通性，不要求在线处理任意未来操作。
面试官考察点
- 能否识别“只增不减”的并查集不变量在删除操作下失效。
- 能否把每条边转换为半开存活区间
[加入时间, 删除时间)。 - 能否用时间线段树把一个区间分解为
O(log q)个节点。 - 能否实现不做路径压缩、只按大小合并的 rollback DSU。
- 能否说明快照、递归返回和查询结果之间的正确性关系。
回答前需要澄清的问题
- 所有操作是否提前可见？若必须在线回答，时间线段树方案不适用。
- 关系是否有唯一 ID？没有 ID 时需要定义删除哪一条重复边。
- 图是否无向？若是有向图，连通性结构和算法都要改写。
- 一条关系是否可能重复添加、删除后再次添加？若允许，必须为每段存活期建立独立区间。
- 查询只问连通性，还是还要返回组件大小、最短路或路径？后者需要扩展状态或换算法。
30 秒回答框架
普通并查集只能合并，不能在不知道内部树结构影响的情况下删除一条边。我会先扫描操作，为每条边建立存活区间 [add, remove)，未删除的边延伸到 q。把区间加入时间线段树，DFS 进入节点时合并该节点覆盖的所有边，在叶子回答查询，离开节点时回滚到进入前的快照。rollback DSU 不做路径压缩，只按大小合并，因此每次合并可记录一次父节点和大小变化；总复杂度是 O((q log q) log n) 量级，空间为 O(n + q log q)。
分步骤深入解答
第一步：确认普通并查集的失效点
普通并查集维护的是当前所有已加入边的合并结果。删除边时，某棵树中的节点可能仍通过其他边连通，也可能需要拆分整棵树；仅凭父指针无法知道应该恢复哪些组件。因此不能在普通并查集上直接调用“反向 union”。
第二步：构造边的存活区间
扫描操作并记录 add 时间。遇到对应 remove 时形成 [add, remove)；叶子时间 t 表示执行第 t 个操作前后的统一时刻，采用半开区间可避免删除时刻仍误用该边。没有删除的关系形成 [add, q)。
第三步：用时间线段树覆盖区间
把每个存活区间放入线段树中完全覆盖它的节点。一个区间最多进入 O(log q) 个节点。节点中的边在该节点整个时间范围内都有效，所以进入节点时合并一次即可，不必在每个叶子重复处理。
第四步：设计可回滚 DSU
使用 parent 和 size 数组。find 只沿父指针向上，不做路径压缩；union 把小树挂到大树，并把被修改的根、旧大小和组件数压入栈。这样每次修改都能在常数时间记录，按大小合并保证树高不超过 O(log n)。
第五步：DFS、快照和恢复
进入节点先保存栈长度 snapshot，再应用节点中的边。到叶子时执行该时间点的 ask。遍历完子节点后，把栈弹回 snapshot。父节点的边因此继续对下一个子树生效，子树临时加入的边不会泄漏。
第六步：给出可执行实现
下面的 Python 伪代码假设操作格式为 ("add", id, u, v)、("remove", id) 和 ("ask", u, v)。它省略输入解析，只展示区间构造、线段树 DFS 和 rollback 核心。
def offline_dynamic_connectivity(n, operations):
q = len(operations)
tree = [[] for _ in range(4 * max(1, q))]
open_edges = {}
intervals = []
asks = [[] for _ in range(q)]
for t, op in enumerate(operations):
if op[0] == "add":
_, edge_id, u, v = op
open_edges[edge_id] = (t, u, v)
elif op[0] == "remove":
_, edge_id = op
start, u, v = open_edges.pop(edge_id)
intervals.append((start, t, u, v))
elif op[0] == "ask":
_, u, v = op
asks[t].append((u, v))
for start, u, v in open_edges.values():
intervals.append((start, q, u, v))
def add_interval(node, left, right, ql, qr, edge):
if ql >= right or qr <= left:
return
if ql <= left and right <= qr:
tree[node].append(edge)
return
mid = (left + right) // 2
add_interval(node * 2, left, mid, ql, qr, edge)
add_interval(node * 2 + 1, mid, right, ql, qr, edge)
if q:
for start, end, u, v in intervals:
if start < end:
add_interval(1, 0, q, start, end, (u, v))
parent = list(range(n))
size = [1] * n
history = []
def find(x):
while parent[x] != x:
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
history.append(None)
return
if size[ra] < size[rb]:
ra, rb = rb, ra
history.append((rb, ra, size[ra]))
parent[rb] = ra
size[ra] += size[rb]
def rollback(snapshot):
while len(history) > snapshot:
change = history.pop()
if change is None:
continue
child, root, old_size = change
parent[child] = child
size[root] = old_size
answers = []
def dfs(node, left, right):
snapshot = len(history)
for u, v in tree[node]:
union(u, v)
if right - left == 1:
answers.extend(find(u) == find(v) for u, v in asks[left])
else:
mid = (left + right) // 2
dfs(node * 2, left, mid)
dfs(node * 2 + 1, mid, right)
rollback(snapshot)
if q:
dfs(1, 0, q)
return answers第七步：证明不变量与复杂度
进入任意线段树节点时，DSU 恰好包含覆盖该节点整个时间范围的边，加上祖先节点已应用的边。子节点新增的边只存在于其子树，返回时回滚，因此叶子时 DSU 等于该时刻所有存活边的并集。每条边进入 O(log q) 个节点，每次合并因按大小合并为 O(log n)，总时间 O(q log q log n)，历史和边存储为 O(n + q log q)。
第八步：比较替代方案与失败场景
若只有新增边和连通查询，普通并查集更简单，摊还复杂度接近常数。若必须在线处理删除，时间线段树不能使用，应考虑动态树或更复杂的全动态图结构。若需要最短路，DSU 只能回答组件关系，不能替代 BFS、Dijkstra 或专门的动态最短路算法。
高质量示范回答
我会先确认操作全部已知且每条关系有稳定 ID。普通并查集只能合并，删除会破坏它维护的组件不变量，所以我扫描操作得到每条边的存活区间 [加入时间, 删除时间)，未删除的边延伸到操作末尾。然后把区间放入时间线段树：DFS 进入节点时合并节点中的边，在叶子回答连通性查询，离开节点时回滚到进入前的历史栈长度。rollback DSU 不做路径压缩，只按大小合并并记录父节点和旧大小，因此树高是 O(log n)。每条边进入 O(log q) 个节点，总时间 O(q log q log n)，空间 O(n + q log q)。如果只增不减，我会改用普通并查集；如果要求在线删除或最短路，则需要换成更强的动态结构。
常见错误
- 直接对删除边做反向 union → 合并不可逆，无法知道要拆分哪些组件 → 改用存活区间和回滚。
- 在 rollback DSU 中使用路径压缩 → 修改路径上的多个父指针却没有完整记录 → 只按大小合并，
find不压缩。 - 把区间写成闭区间
[add, remove]→ 删除时刻仍把边算作存活 → 使用半开区间[add, remove)。 - 每个叶子重新合并所有边 → 复杂度退化且失去线段树意义 → 在覆盖整个时间范围的节点合并一次。
- 只恢复父节点不恢复
size→ 后续按大小合并的树形被污染 → 每次修改记录旧大小并一起恢复。 - 把离线方法承诺为在线方案 → 新操作到达后时间区间未知 → 先确认交互模型，再选择数据结构。
追问及应对
如果同一个关系 ID 会被删除后再次添加，怎么改？
每次 add 都创建一条新的开放记录，remove 只关闭当前未关闭的那一段。这样同一 ID 会产生多个不重叠区间，不能覆盖旧区间或复用同一个起点。
如果还要查询当前连通分量大小，能否复用方案？
可以在 DSU 中维护根的 size，find 返回根后读取大小；回滚时恢复旧大小。若还要维护组件数量、每个组件的聚合值，也要把每次可变字段的旧值压栈，并确保聚合操作可逆。
如果 q 很大、递归深度或内存成为瓶颈，怎么办？
先确认 O(q log q) 的区间存储是否可接受，再用显式 DFS 栈替代递归、压缩边结构或按时间块处理。不能因为栈溢出就启用路径压缩，应该保持可回滚不变量。
如果必须在线支持删除，为什么不能把区间方案硬改成在线？
区间方案要知道一条边何时删除，才能把它放进时间线段树。在线场景中未来删除时间未知，预处理阶段无法建立完整区间；应改用支持删除的动态连通性结构，并重新评估实现复杂度和查询延迟。