朴素算法Bare Algo

并查集

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

算法题

(8)

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

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

547. 省份数量

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

684. 冗余连接

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

261. 以图判树

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

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

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

721. 账户合并

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

1202. 交换字符串中的元素

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

990. 等式方程的可满足性

中等
数组字符串并查集图

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

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

200. 岛屿数量

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

128. 最长连续序列

中等
数组哈希表并查集