网站建设全网推广莆田网站建设哪家好

网站建设全网推广,莆田网站建设哪家好,wordpress相册模板,wordpress首页调用缩略图写在前面#xff1a;最近刷 LeetCode 遇到一道题#xff08;2092. Find All People With Secret#xff09;#xff0c;题目要求模拟“秘密”在专家之间的传播过程。我一开始想到用 set BFS#xff0c;后来又看到有人用并查集#xff08;Union-Find#xff09;解法。于…写在前面最近刷 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(keylambdax:x[2])i0whileilen(meetings):# 收集同一时间的所有会议建图graphdefaultdict(list)while同一时间:x,ymeeting graph[x].append(y)graph[y].append(x)i1# BFS从 known 中已在图里的人出发queuedeque([pforpingraphifpinknown])visitedset(queue)whilequeue:curqueue.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)# 分组groupsdefaultdict(set)forpinpeople_in_this_time:groups[find(p)].add(p)# 检查哪些 group 有 known 的人forgroupingroups.values():ifany(pinknownforpingroup):known|group优缺点✅ 并查集操作快近 O(1)。❌ 但要遍历所有参会者即使他们和秘密无关。❌ 容易写错比如忘记重置 UF。⚖️ 深入对比SetBFS vs 并查集维度Set BFS/DFS并查集Union-Find适用场景离线、分批、需状态传播在线动态连通性、仅需判断连通时间复杂度O(M log M M)O(M log M M α(N))常数开销较小只遍历相关部分稍大需初始化、分组剪枝能力✅ 强从已知出发❌ 弱必须处理所有节点代码难度简单直观易错UF 隔离问题能否获取路径✅ 可以❌ 不行在线查询支持❌ 不支持✅ 支持结论对于本题这类“分阶段、状态传播”的问题Set BFS 更合适。但对于“边动态加入、频繁查询连通性”的问题如 Kruskal 最小生成树并查集不可替代。 那么问题来了所有并查集解法都能被 SetBFS 替代吗答案是不能。✅ 可以替代的情况图是静态的或离线分批构建的。你需要传播状态如“知道秘密”、过滤条件、剪枝。你关心连通块内部结构比如谁传给谁。例如LeetCode 2092、朋友圈、岛屿数量等。❌ 难以替代的情况在线动态连通性边一条条来中间不断问“x 和 y 连通吗”BFS 每次都要重建图 遍历 → O(nm) 每次太慢。并查集每次 O(α(n))快得多。只需要判断连通性不需要遍历并查集内存更省操作更快。高频合并集合如 Kruskal 算法必须高效判断加边是否成环。 类比理解并查集≈ “户口本管理员”→ 你问“A 和 B 是一家人吗”→ 他秒查户口本告诉你“是”或“不是”但不知道家里谁做饭、谁带娃。BFS/DFS set≈ “社区社工上门走访”→ 你让他从 A 家出发看看能串门到哪些人家。→ 他不仅能告诉你连通性还能记录路径、传播消息、收集需求。所以任务不同工具不同。