并查集的典型应用：统计省份数量

题目来源https://leetcode.com/problems/number-of-provinces/description/有 n 个城市其中一些彼此直接相连另一些则没有直接相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份定义为一组直接或间接相连的城市且这组城市之外不包含其他与该组内城市相连的城市。给你一个 n x n 矩阵 isConnected其中 isConnected[i][j] 1 表示第 i 个城市和第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。请你返回矩阵中省份的总数量。【解】这道题是 LeetCode 547本质上就是求无向图的连通分量个数与并查集的经典用法完全吻合。解题思路问题转化有n个城市isConnected[i][j] 1表示城市i与j直接相连。省份 连通分量。求图中连通分量的总数。并查集建模初始时每个城市自成一个省份省份数量count n。遍历矩阵的上三角部分i j若isConnected[i][j] 1说明两个城市直接相连应属于同一个省份。调用union(i, j)若合并成功之前不在同一集合则当前省份数量减1。最终count就是省份的总数。复杂度分析时间O(n^2 * α(n))≈O(n^2)其中α(n)是反阿克曼函数可以视为常数。空间O(n)用于存储parent和rank数组。代码实现PythonclassUnionFind: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):rootXself.find(x)rootYself.find(y)ifrootXrootY:returnFalse# 已在同一集合合并失败# 按秩合并ifself.rank[rootX]self.rank[rootY]:self.parent[rootX]rootYelifself.rank[rootX]self.rank[rootY]:self.parent[rootY]rootXelse:self.parent[rootY]rootX self.rank[rootX]1self.count-1# 成功合并连通分量减1returnTrueclassSolution: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解题步骤解析第 3 行并查集类中额外维护count表示当前连通分量个数初始化为n。第 1117 行find采用递归写法同时进行路径压缩使得后续查找近似常数时间。第 1931 行union方法在成功合并两个不同集合时将count减 1其余逻辑与标准按秩合并一致。第 3638 行双重循环只遍历i j的部分避免重复和自环。若两城市直接相连则尝试合并。第 39 行最后直接返回uf.count即为省份总数。以下是使用 C 语言实现的并查集解法完全按照考研及算法题的标准写法编写包含路径压缩与按秩合并优化。#includestdlib.h// 查找操作路径压缩intfind(int*parent,intx){if(parent[x]!x)parent[x]find(parent,parent[x]);// 递归压缩路径returnparent[x];}// 合并操作按秩合并并通过指针修改连通分量计数voidunionSet(int*parent,int*rank,int*count,intx,inty){introotXfind(parent,x);introotYfind(parent,y);if(rootXrootY)return;// 已在同一集合不合并// 将较矮的树挂到较高的树下if(rank[rootX]rank[rootY]){parent[rootX]rootY;}elseif(rank[rootX]rank[rootY]){parent[rootY]rootX;}else{parent[rootY]rootX;rank[rootX];// 高度相等时树高增1}(*count)--;// 连通分量数减1}intfindCircleNum(int**isConnected,intisConnectedSize,int*isConnectedColSize){intnisConnectedSize;// 动态分配并查集所需数组int*parent(int*)malloc(n*sizeof(int));int*rank(int*)malloc(n*sizeof(int));// 初始化每个城市自成一个集合for(inti0;in;i){parent[i]i;rank[i]0;}intprovincesn;// 初始省份数量等于城市数量// 遍历矩阵的上三角部分避免重复for(inti0;in;i){for(intji1;jn;j){if(isConnected[i][j]1){unionSet(parent,rank,provinces,i,j);}}}intresultprovinces;// 释放内存free(parent);free(rank);returnresult;}说明函数签名严格按照 LeetCode 547 题的 C 接口要求int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize)其中isConnectedSize为城市数量nisConnectedColSize为每行的列数数组可不用。并查集核心操作find递归实现路径压缩使树扁平化均摊近乎O(1)。unionSet按秩合并用rank记录树高上界避免树无故增高合并成功时将省份计数provinces减 1。复杂度分析时间O(n^2 · α(n))≈O(n^2)其中α(n)为反阿克曼函数可视为常数。空间O(n)仅需两个长度为n的数组。