当前位置：首页 > news >正文

算法学习记录18——并查集 vs Set + BFS/DFS

news 2026/6/28 14:08:10

写在前面：最近刷 LeetCode 遇到一道题（2092. Find All People With Secret），题目要求模拟“秘密”在专家之间的传播过程。我一开始想到用set+ BFS，后来又看到有人用并查集（Union-Find）解法。于是我就开始思考：这两种方法到底有什么区别？能不能互相替代？哪种更高效？这篇笔记就是我对这个问题的探索和总结，希望能帮到未来的自己，也欢迎你一起学习！

🧩 问题背景回顾

题目大意：

有n个专家（编号 0 到 n-1）。
专家 0 在时间 0 把秘密告诉了firstPerson。
之后，在一系列会议中（每个会议是[x, y, time]），如果其中一人知道秘密，另一人立刻也知道。
同一时间点的多场会议可以“瞬时”传播秘密（即形成连通分量，只要有一人知道，整个连通块都知道）。
问最终哪些专家知道秘密？

关键点：按时间分组处理，每组内做连通性传播。

✅ 我的第一反应：用`set`+ BFS

思路

用一个set（比如叫known）记录当前知道秘密的人。
把所有会议按时间排序，相同时间的归为一组。
对每一组：
- 构建无向图（邻接表）。
- 从known中已知的人出发，BFS 遍历整个连通分量。
- 把遍历到的所有人加入known。

代码核心片段（简化版）

known={0,firstPerson}meetings.sort(key=lambdax:x[2])i=0whilei<len(meetings):# 收集同一时间的所有会议，建图graph=defaultdict(list)while同一时间:x,y=meeting graph[x].append(y)graph[y].append(x)i+=1# BFS：从 known 中已在图里的人出发queue=deque([pforpingraphifpinknown])visited=set(queue)whilequeue:cur=queue.popleft()fornbingraph[cur]:ifnbnotinvisited:visited.add(nb)queue.append(nb)known|=visited# 合并新知道秘密的人

优点

逻辑直观：就像真的在“传播秘密”。
自动剪枝：只遍历与已知者连通的部分，无关节点完全不碰。
效率高：实测在 LeetCode 上跑得很快。

🔁 后来我尝试了并查集（Union-Find）

思路

同样按时间分组。
对每组会议：
- 收集所有涉及的人。
- 新建一个并查集（⚠️关键！不能复用之前的，否则会跨时间错误传播）。
- 把每对会议参与者 union 起来。
- 按根节点分组，检查每个连通分量是否包含known中的人。
- 如果包含，就把整个分量加入known。

注意事项

必须为每个时间点单独建 UF！这是最容易出错的地方。
即使某分量只有一个人知道秘密，也要把整个分量加进去。

代码片段（关键部分）

# 每个时间点新建 parent 字典parent={p:pforpinpeople_in_this_time}deffind(x):ifparent[x]!=x:parent[x]=find(parent[x])returnparent[x]forx,yinmeetings_at_this_time:union(x,y)# 分组groups=defaultdict(set)forpinpeople_in_this_time:groups[find(p)].add(p)# 检查哪些 group 有 known 的人forgroupingroups.values():ifany(pinknownforpingroup):known|=group

优缺点

✅ 并查集操作快（近 O(1)）。
❌ 但要遍历所有参会者，即使他们和秘密无关。
❌ 容易写错（比如忘记重置 UF）。

⚖️ 深入对比：Set+BFS vs 并查集

维度	Set + BFS/DFS	并查集（Union-Find）
适用场景	离线、分批、需状态传播	在线动态连通性、仅需判断连通
时间复杂度	O(M log M + M)	O(M log M + M α(N))
常数开销	较小（只遍历相关部分）	稍大（需初始化、分组）
剪枝能力	✅ 强（从已知出发）	❌ 弱（必须处理所有节点）
代码难度	简单直观	易错（UF 隔离问题）
能否获取路径	✅ 可以	❌ 不行
在线查询支持	❌ 不支持	✅ 支持

💡结论：
对于本题这类“分阶段、状态传播”的问题，Set + BFS 更合适。
但对于“边动态加入、频繁查询连通性”的问题（如 Kruskal 最小生成树），并查集不可替代。

🤔 那么问题来了：所有并查集解法都能被 Set+BFS 替代吗？

答案是：不能。

✅ 可以替代的情况

图是静态的或离线分批构建的。
你需要传播状态（如“知道秘密”）、过滤条件、剪枝。
你关心连通块内部结构（比如谁传给谁）。

例如：LeetCode 2092、朋友圈、岛屿数量等。

❌ 难以替代的情况

在线动态连通性：边一条条来，中间不断问“x 和 y 连通吗？”
- BFS 每次都要重建图 + 遍历 → O(n+m) 每次，太慢。
- 并查集每次 O(α(n))，快得多。
只需要判断连通性，不需要遍历：
- 并查集内存更省，操作更快。
高频合并集合：
- 如 Kruskal 算法，必须高效判断加边是否成环。

🧠 类比理解

并查集≈ “户口本管理员”
→ 你问：“A 和 B 是一家人吗？”
→ 他秒查户口本告诉你“是”或“不是”，但不知道家里谁做饭、谁带娃。
BFS/DFS + set≈ “社区社工上门走访”
→ 你让他从 A 家出发，看看能串门到哪些人家。
→ 他不仅能告诉你连通性，还能记录路径、传播消息、收集需求。