Union Find 并查集算法原理及应用

文章预览

作者：labuladong 公众号：labuladong 读完本文，可以去力扣解决如下题目： 323. 无向图中的连通分量数目（ 中等 ） 130. 被围绕的区域（ 中等 ） 990. 等式方程的可满足性（ 中等 ） 记得我之前在讲  图论算法基础  时说图论相关的算法不会经常考，但最近被打脸了，因为一些读者和我反馈近期求职面试涉及很多图论相关的算法，可能是因为环境不好所以算法这块更卷了吧。 常见的图论算法我都已经写过了，这里按难度顺序列举一下： 图论算法基础 二分图判定算法及应用 环检测/拓扑排序算法及应用 并查集算法及应用（本文） Kruskal 最小生成树算法及应用 Prim 最小生成树算法及应用 Dijkstra 算法模板及应用 并查集（Union-Find）算法是一个专门针对「动态连通性」的算法，我之前写过两次，因为这个算法的考察频率高，而且它也是最小生成树算法的前置 ………………………………