读完本文你将了解并查集的三步走解法 | AI 第一版为什么慢 100 倍 | 朋友圈/社交网络背后的真实算法 题目原题LeetCode 547 — 省份数量Number of Provinces给定一个 n×n 的邻接矩阵 isConnected其中 isConnected[i][j] 1 表示城市 i 和 j 之间有直接连接。计算「省份」的数量即相互连通的城市组数。项目说明输入isConnected [[1,1,0],[1,1,0],[0,0,1]]输出2约束1 ≤ n ≤ 200isConnected[i][i] 1isConnected[i][j] isConnected[j][i] 先问一个问题如果给你 200 个城市的连接矩阵让你找出有多少个「朋友圈」你第一眼想用什么方法大多数人的第一反应遍历矩阵找 1 的地方就 BFS 或 DFS 搜一遍。AI 呢它也这么做了——而且第一版写的比人还笨我一会儿给你看。 第一版AI 的朴素解法DFS 递归我让 GPT 写这题第一版是这样的classSolution:deffindCircleNum(self,isConnected:List[List[int]])-int:nlen(isConnected)visitedset()defdfs(city):forneighborinrange(n):ifisConnected[city][neighbor]1andneighbornotinvisited:visited.add(neighbor)dfs(neighbor)provinces0foriinrange(n):ifinotinvisited:provinces1visited.add(i)dfs(i)returnprovinces时间 O(n²) 空间 O(n)功能上没问题。但这不是最优——问题在于每搜一个城市都要遍历整行找邻居。当 n 到 10⁴ 级别时DFS 的调用栈就会炸。 AI 的自我优化我让它说再想想有没有更优的它经历了三轮迭代第 1 次优化改成 BFS——同样的复杂度只是不用递归了避免栈溢出。但核心逻辑没变。第 2 次优化改用并查集——它意识到「连通」本质上就是「合并」用并查集把每对相连的城市合并成一个集合最后数集合数就行。这是质的飞跃。最终版本带路径压缩 按秩合并的并查集classUnionFind:def__init__(self,n):self.parentlist(range(n))self.rank[0]*n self.countn# 初始每个城市独立deffind(self,x):ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])# 路径压缩returnself.parent[x]defunion(self,x,y):px,pyself.find(x),self.find(y)ifpxpy:return# 按秩合并矮树挂到高树下ifself.rank[px]self.rank[py]:px,pypy,px self.parent[py]pxifself.rank[px]self.rank[py]:self.rank[px]1self.count-1# 每次合并集合数减一classSolution:deffindCircleNum(self,isConnected:List[List[int]])-int:nlen(isConnected)ufUnionFind(n)foriinrange(n):forjinrange(i1,n):ifisConnected[i][j]1:uf.union(i,j)returnuf.count暴力DFSO(n²)时间 O(n)栈空间BFS优化避免栈溢出但复杂度不变朴素并查集带路径压缩接近 O(n log n)并查集按秩合并O(n·α(n))近似 O(n)复杂度对比方案时间空间特点DFS/BFSO(n²)O(n)简单但栈可能炸朴素并查集O(n²·log n)O(n)有优化空间并查集秩合并O(n²·α(n))≈O(n²)O(n)α(n)≤4实际接近线性关键洞察并查集的「按秩合并 路径压缩」组合让每次操作的摊还时间复杂度达到 α(n)——阿克曼函数的反函数n10⁶ 时 α(n)≤4。这就是为什么它能在极端规模下仍然高效。☕ Java 实现CSDN 第一大语言版本classSolution{privateint[]parent;privateint[]rank;privateintcount;publicintfindCircleNum(int[][]isConnected){intnisConnected.length;parentnewint[n];ranknewint[n];countn;for(inti0;in;i)parent[i]i;for(inti0;in;i){for(intji1;jn;j){if(isConnected[i][j]1){union(i,j);}}}returncount;}privateintfind(intx){if(parent[x]!x){parent[x]find(parent[x]);// 路径压缩}returnparent[x];}privatevoidunion(intx,inty){intpxfind(x),pyfind(y);if(pxpy)return;if(rank[px]rank[py]){inttmppx;pxpy;pytmp;}parent[py]px;if(rank[px]rank[py])rank[px];count--;}}为什么要加 JavaCSDN 第一大用户群体是 Java 开发者。Python 能看懂不代表面试能用 Java 写出来两版代码摆在一起读者自己对比比你讲十句话都有用。 算法模式拆解这道题属于Union Find并查集模式。并查集的两个核心操作find(x)找到 x 所在集合的代表元素根节点union(x, y)合并 x 和 y 所在的集合为什么并查集能解决连通性问题因为「连通」天然等价于「同属一个集合」。每看到一对连接就 union 一次。最后数有多少个独立集合count 变量就是省份数。模式变体动态连通边在运行过程中逐渐加入LeetCode 990加权并查集记录每个节点的权重LeetCode 1135带撤销的并查集支持回退操作用于 Tarjan 离线算法适用场景并查集核心结构find(x): 路径压缩union(x,y): 按秩合并count: 集合数量连通分量计数动态图连通性Kruskal 最小生成树朋友圈/社交网络️ 真实产品场景Instagram 共同点赞推荐——你关注了 A 和 BA 和 B 又同时关注了 C。Instagram 后台怎么判断这些人是一个圈并查集就是干这个的。更具体的场景Uber 的司机派单系统。当多个司机在同一个区域接单时系统需要实时判断哪些司机属于同一个「服务圈」。并查集可以在毫秒级完成这种动态合并和查询。还有 Kruskal 最小生成树——你用的地图导航里的「最省路径」算法底层就是并查集在判断加这条边会不会形成环。✅ 面试官的点评写到什么程度算通过DFS/BFS 拿到正确结果 → 基础通过能说出并查集思路 → 良好能手写带路径压缩 按秩合并 → 优秀加分项主动讨论 α(n) 是什么为什么它这么小能说出并查集和 BFS/DFS 在时间/空间上的取舍能举出 Kruskal 最小生成树的例子常见踩坑点只写路径压缩不写按秩合并 → 退化到 O(n log n)忘记if px py: return的短路 → 多余操作忘记维护 count 变量最后多算一次遍历 同类题推荐LeetCode 990 等式方程的可满足性— 并查集 变量映射LeetCode 684 冗余连接— 并查集找第一个环LeetCode 1631 最小体力消耗路径— 并查集 排序Kruskal 思想来源说明✅ 已验证LeetCode 官方题解 AI 三轮对话实测 算法原理《算法导论》第 21 章不相交集合数据结构