朴素算法Bare Algo

并查集

基础连通分量、冗余连接及带权并查集。

算法题

(8)

第 1 阶段:先掌握连通性判定与成环检测

先把并查集最核心的两个目标练熟:判断两个点是否连通,以及加入新边后是否产生环。

547. 省份数量

中等
深度优先搜索广度优先搜索并查集图

684. 冗余连接

中等
深度优先搜索广度优先搜索并查集图

261. 以图判树

中等
深度优先搜索广度优先搜索并查集图

第 2 阶段:学会按连通分量做分组与约束合并

这一阶段重点是把对象抽象成节点并按关系连边,再按连通分量聚合信息或校验约束是否冲突。

721. 账户合并

中等
数组哈希表字符串深度优先搜索广度优先搜索并查集

1202. 交换字符串中的元素

中等
数组哈希表字符串深度优先搜索广度优先搜索并查集

990. 等式方程的可满足性

中等
数组字符串并查集图

第 3 阶段:处理网格建模与哈希映射变体

最后把并查集用于二维网格和非连续值域问题。核心是节点映射方式,以及合并时机和统计口径。

200. 岛屿数量

中等
深度优先搜索广度优先搜索并查集矩阵

128. 最长连续序列

中等
数组哈希表并查集

实际应用

(5)

社交网络分群

中等

社交关系常按连通性划分群组并统计社群,提升处理效率。

并查集社交网络用户关系

实时连通性检测

中等

连通状态常动态合并节点并快速查询结果,提升处理效率。

并查集路径压缩实时系统协作应用

图像区域合并

困难

相邻像素区域常按连通规则合并为统一块,提升处理效率。

并查集图像处理区域分割

网络冗余链路检测

简单

网络配置常检测冗余链路与潜在环路问题,提升处理效率。

并查集环检测网络拓扑系统运维

权限组合并

中等

权限组关系常按等价集合合并重复配置,提升处理效率。

并查集权限系统用户管理