离线排序 + 逐步激活 + 并查集

并查集、MST 与离线激活 · HTML

数学 / 逻辑形态

边或点带 key；查询只依赖 key 与阈值 t 的比较。排序事件与查询，使可用集合单向增长。

识别信号

• 许多不同阈值下的连通查询
• 越过阈值后对象永久可用
• 查询允许离线重排
• 激活只引起邻近组件合并
• 逐查询 BFS 会重复扫描

容易误判的相似信号

核心不变量

回答阈值 t 前，恰好所有满足条件的事件已激活，DSU 组件等于该阈值下真实连通块。

状态、转移与处理顺序

Python 骨架

def offline_connectivity(n, edges, queries):
    p = list(range(n))
    def find(x):
        while x != p[x]:
            p[x] = p[p[x]]; x = p[x]
        return x
    def union(a, b):
        a, b = find(a), find(b)
        if a != b: p[b] = a
    edges = sorted(edges)  # (weight,u,v)
    order = sorted((lim, i, u, v) for i, (lim,u,v) in enumerate(queries))
    ans, j = [False] * len(queries), 0
    for lim, i, u, v in order:
        while j < len(edges) and edges[j][0] <= lim:
            _, a, b = edges[j]; union(a, b); j += 1
        ans[i] = find(u) == find(v)
    return ans

正确性思路

1. 排序保证扫描到 lim 时，所有且仅有 key<=lim 的事件位于指针左侧。
2. 每个激活边执行 union，所以 DSU 与激活子图组件一致。
3. 查询只读取当前状态，得到原阈值定义下的连通性。
4. 按原下标回填使重排不改变输出顺序。

复杂度

边界条件

• 严格小于与小于等于影响同值顺序
• 无事件时仍要处理自连通
• 阈值在所有 key 之外
• 相同 key 事件需成批处理
• 重复查询仍要保留各自下标

错误模式

选择与排除规则

• 查询可重排且可用集合单调扩张：选离线激活。
• 只有单查询时，直接搜索可能更简单。
• 先明确 < 还是 <=，再定事件顺序。
• 点激活时只与已激活邻居 union。

相关模板

原创微型例子

Recall prompts

• 离线重排后为何答案仍正确？
• < 与 <= 如何改变同值顺序？
• 点激活后应与哪些对象合并？

我的补充