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

题目来源：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，本质上就是求无向图的连通分量个数，与并查集的经典用法完全吻合。

解题思路

1. 问题转化

   • 有n个城市，isConnected[i][j] = 1表示城市i与j直接相连。
   • 省份 = 连通分量。求图中连通分量的总数。

2. 并查集建模

   • 初始时，每个城市自成一个省份，省份数量count = n。
   • 遍历矩阵的上三角部分（i < j），若isConnected[i][j] == 1，说明两个城市直接相连，应属于同一个省份。
   • 调用union(i, j)，若合并成功（之前不在同一集合），则当前省份数量减1。
   • 最终count就是省份的总数。

3. 复杂度分析

   • 时间：O(n^2 * α(n))≈O(n^2)，其中α(n)是反阿克曼函数，可以视为常数。
   • 空间：O(n)，用于存储parent和rank数组。

代码实现（Python）

classUnionFind:def__init__(self,n):self.parent=list(range(n))self.rank=[0]*n self.count=n# 连通分量个数deffind(self,x):ifself.parent[x]!=x:self.parent[x]=self.find(self.parent[x])# 路径压缩returnself.parent[x]defunion(self,x,y):rootX=self.find(x)rootY=self.find(y)ifrootX==rootY: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:n=len(isConnected)uf=UnionFind(n)foriinrange(n):forjinrange(i+1,n):# 只需遍历上三角ifisConnected[i][j]==1:uf.union(i,j)returnuf.count

解题步骤解析

• 第 3 行：并查集类中额外维护count，表示当前连通分量个数，初始化为n。
• 第 11～17 行：find采用递归写法，同时进行路径压缩，使得后续查找近似常数时间。
• 第 19～31 行：union方法在成功合并两个不同集合时，将count减 1，其余逻辑与标准按秩合并一致。
• 第 36～38 行：双重循环只遍历i < j的部分，避免重复和自环。若两城市直接相连，则尝试合并。
• 第 39 行：最后直接返回uf.count即为省份总数。

---

以下是使用 C 语言实现的并查集解法，完全按照考研及算法题的标准写法编写，包含路径压缩与按秩合并优化。

#include<stdlib.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){introotX=find(parent,x);introotY=find(parent,y);if(rootX==rootY)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){intn=isConnectedSize;// 动态分配并查集所需数组int*parent=(int*)malloc(n*sizeof(int));int*rank=(int*)malloc(n*sizeof(int));// 初始化：每个城市自成一个集合for(inti=0;i<n;i++){parent[i]=i;rank[i]=0;}intprovinces=n;// 初始省份数量等于城市数量// 遍历矩阵的上三角部分，避免重复for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){if(isConnected[i][j]==1){unionSet(parent,rank,&provinces,i,j);}}}intresult=provinces;// 释放内存free(parent);free(rank);returnresult;}

说明

1. 函数签名
   严格按照 LeetCode 547 题的 C 接口要求：
   int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize)
   其中isConnectedSize为城市数量n，isConnectedColSize为每行的列数数组（可不用）。

2. 并查集核心操作

   • find：递归实现，路径压缩使树扁平化，均摊近乎O(1)。
   • unionSet：按秩合并（用rank记录树高上界），避免树无故增高；合并成功时将省份计数provinces减 1。

3. 复杂度分析

   • 时间：O(n^2 · α(n))≈O(n^2)，其中α(n)为反阿克曼函数，可视为常数。
   • 空间：O(n)，仅需两个长度为n的数组。