《并查集：算法中的高效集合操作利器》：一文带你掌握并查集数据结构
系列文章目录
文章目录
一、认识并查集
1.并查集的定义
并查集是一种用于管理不相交集合（Disjoint Set）的数据结构。它主要用于处理一些需要动态维护集合的合并和查询操作的问题。并查集的核心功能是高效地支持以下两个基本操作：
Find（查询）：确定某个元素属于哪一个集合。
Union（合并）：将两个元素所在的集合合并为一个集合。
2.基本概念
2.1.集合的表示
并查集通过一个数组（通常称为parent数组）来表示每个元素的“父节点”，从而形成一个森林结构。每个集合用一个树来表示，树的根节点即为该集合的代表元素。
例如，假设我们有5个元素（0, 1, 2, 3, 4），初始时每个元素都是一个独立的集合：
0 1 2 3 4
对应的parent数组为：
[0, 1, 2, 3, 4]
每个元素的父节点指向自己，表示每个元素都是一个独立的集合。
2.2.合并操作
当我们需要将两个元素所在的集合合并时，可以通过将一个集合的根节点指向另一个集合的根节点来实现。例如，将元素1和元素0所在的集合合并：
0 1 2 3 4
\ /
1
此时对应的parent数组变为：[1, 1, 2, 3, 4]
此时，元素1和元素0属于同一个集合，集合的根节点是1。
2.3.查询操作
查询某个元素属于哪个集合时，我们只需要找到该元素所在树的根节点。例如，查询元素2属于哪个集合：find(0) -> find(1) -> 1
元素0的根节点是1，因此元素2属于根节点为1的集合。
3.基本操作
3.1初始化
初始化时，每个元素的父节点指向自己，表示每个元素初始时都是一个独立的集合。
publicclassUnionFind{privateint[] parent;// 父节点数组privateint[] rank;// 秩数组（用于按秩合并）// 初始化并查集publicUnionFind(int n){ parent =newint[n]; rank =newint[n];for(int i =0; i < n; i++){ parent[i]= i;// 每个元素的父节点初始化为自身 rank[i]=0;// 每个元素的秩初始化为0}}}3.2.查找
查找操作的目的是找到某个元素所在的集合的根节点。为了提高效率，通常会使用路径压缩技术，即将查找路径上的所有节点直接指向根节点。
// 查找操作，带路径压缩publicintfind(int x){if(parent[x]!= x){ parent[x]=find(parent[x]);// 路径压缩}return parent[x];}3.3.合并
合并操作是将两个元素所在的集合合并为一个集合。通常会使用**按秩合并（Union by Rank）或按大小合并（Union by Size）**来优化合并操作，避免树变得过高。
// 合并操作，带按秩合并publicvoidunion(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX != rootY){if(rank[rootX]> rank[rootY]){ parent[rootY]= rootX;}elseif(rank[rootX]< rank[rootY]){ parent[rootX]= rootY;}else{ parent[rootY]= rootX; rank[rootX]+=1;}}}4.优化技巧
4.1.路径压缩
路径压缩是在查找操作中，将查找路径上的所有节点直接指向根节点，从而减少后续查找的深度。路径压缩的实现非常简单，只需要在find函数中添加一行代码即可。
publicintfind(int x){if(parent[x]!= x){ parent[x]=find(parent[x]);// 路径压缩}return parent[x];}4.2.按秩合并
按秩合并是在合并操作中，总是将秩（树的高度或深度）较小的树合并到秩较大的树上，从而避免树变得过高。秩可以用一个额外的数组rank来记录。
publicvoidunion(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX != rootY){if(rank[rootX]> rank[rootY]){ parent[rootY]= rootX;}elseif(rank[rootX]< rank[rootY]){ parent[rootX]= rootY;}else{ parent[rootY]= rootX; rank[rootX]+=1;}}}5.代码完整实例
publicclassUnionFind{privateint[] parent;// 父节点数组privateint[] rank;// 秩数组（用于按秩合并）// 初始化并查集publicUnionFind(int n){ parent =newint[n]; rank =newint[n];for(int i =0; i < n; i++){ parent[i]= i;// 每个元素的父节点初始化为自身 rank[i]=0;// 每个元素的秩初始化为0}}// 查找操作，带路径压缩publicintfind(int x){if(parent[x]!= x){ parent[x]=find(parent[x]);// 路径压缩}return parent[x];}// 合并操作，带按秩合并publicvoidunion(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX != rootY){if(rank[rootX]> rank[rootY]){ parent[rootY]= rootX;}elseif(rank[rootX]< rank[rootY]){ parent[rootX]= rootY;}else{ parent[rootY]= rootX; rank[rootX]+=1;}}}// 判断两个元素是否属于同一个集合publicbooleanisConnected(int x,int y){returnfind(x)==find(y);}// 打印当前的父节点数组（用于调试）publicvoidprintParent(){for(int i =0; i < parent.length; i++){System.out.print(parent[i]+" ");}System.out.println();}// 打印当前的秩数组（用于调试）publicvoidprintRank(){for(int i =0; i < rank.length; i++){System.out.print(rank[i]+" ");}System.out.println();}}// 测试并查集publicclassMain{publicstaticvoidmain(String[] args){int n =10;// 假设有10个元素UnionFind uf =newUnionFind(n);// 合并一些元素 uf.union(1,2); uf.union(2,5); uf.union(6,7); uf.union(3,8); uf.union(8,9);// 查询一些元素是否连通System.out.println("Is 1 and 5 connected? "+ uf.isConnected(1,5));// trueSystem.out.println("Is 6 and 7 connected? "+ uf.isConnected(6,7));// trueSystem.out.println("Is 1 and 3 connected? "+ uf.isConnected(1,3));// false// 打印当前的父节点数组和秩数组System.out.print("Parent array: "); uf.printParent();System.out.print("Rank array: "); uf.printRank();}}6.应用场景
6.1.图的连通性
并查集可以用于判断图中是否存在环，或者判断图中两个节点是否连通。例如，在最小生成树（Kruskal算法）中，使用并查集来判断边是否会形成环。
6.2.社交网络分析
在社交网络中，可以使用并查集来判断两个用户是否属于同一个社交圈子。
6.3.动态连通性问题
并查集可以动态地处理元素的合并和查询操作，适用于需要频繁更新连通性状态的场景。
7.时间复杂度
初始化：O(n)
查找（带路径压缩）：几乎为常数时间，摊还复杂度为O(α(n)) ，其中α(n) 是阿克曼函数的反函数，增长非常缓慢。
合并（带按秩合并）：几乎为常数时间，摊还复杂度为O(α(n)) 。
二、例题实战
例题一
力扣778、水位上升的泳池中游泳
1.题目描述：
在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。
当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。
示例1：
示例2：
2.算法思路：
这道题目可以用并查集来解决，原因在于并查集能够高效地处理动态连通性问题，即在动态变化的环境中判断两个点是否连通。在这个问题中，随着时间的推移（水位的上升），原本不连通的平台可能会因为水位的升高而变得连通。并查集可以动态地维护这些平台之间的连通性，从而帮助我们找到从起点到终点的最短时间。
动态连通性：随着时间的推移，水位上升，原本不连通的平台可能会变得连通。并查集可以动态地处理这种连通性的变化。每当水位上升到某个高度时，所有高度小于或等于该水位的平台都会被淹没，这些平台之间可能会形成新的连通关系。
高效性：并查集的查找和合并操作在路径压缩和按秩合并的优化下，几乎可以认为是常数时间复杂度（摊还复杂度为 O(α(n)) ）这使得它在处理大规模数据时非常高效。
3.解题思路：
1.初始化并查集：
初始化一个并查集，将矩阵中的每个平台视为一个独立的集合。
2.排序平台高度：
将矩阵中的所有平台高度提取出来，并按高度从小到大排序。这样我们可以按顺序处理每个平台，确保水位逐渐上升。
3.动态合并平台：
按高度从小到大的顺序处理每个平台。对于每个平台，检查其四个方向（上、下、左、右）的相邻平台。如果相邻平台已经被淹没（即高度小于或等于当前水位），则将当前平台与相邻平台合并到同一个集合中。
4.判断连通性：
每次合并后，检查起点（0, 0）和终点（n-1, n-1）是否连通。如果连通，则当前水位即为所需最少时间。
4.代码示例：
privateintN;// 网格的边长// 定义四个方向的移动：右、左、下、上publicstaticfinalint[][] DIRECTIONS ={{0,1},{0,-1},{1,0},{-1,0}};publicintswimInWater(int[][] grid){this.N= grid.length;// 获取网格边长int len =N*N;// 网格中总的格子数// 下标：方格的高度，值：对应在方格中的坐标int[] index =newint[len];// 建立高度到坐标的映射关系for(int i =0; i <N; i++){for(int j =0; j <N; j++){ index[grid[i][j]]=getIndex(i, j);// 将高度为grid[i][j]的格子映射到坐标(i,j)}}UnionFind unionFind =newUnionFind(len);// 初始化并查集// 按照时间（高度）顺序处理每个格子for(int i =0; i < len; i++){int x = index[i]/N;// 根据索引获取当前格子的行坐标int y = index[i]%N;// 根据索引获取当前格子的列坐标// 检查四个方向的相邻格子for(int[] direction : DIRECTIONS){int newX = x + direction[0];// 计算新行坐标int newY = y + direction[1];// 计算新列坐标// 如果新坐标在网格范围内且相邻格子的高度小于等于当前时间if(inArea(newX, newY)&& grid[newX][newY]<= i){// 将当前格子与相邻格子连接 unionFind.union(index[i],getIndex(newX, newY));}// 检查起点(0,0)和终点(N-1,N-1)是否连通if(unionFind.isConnected(0, len -1)){return i;// 如果连通，返回当前时间}}}return-1;// 如果始终未连通，返回-1}// 将二维坐标转换为一维索引privateintgetIndex(int x,int y){return x *N+ y;}// 检查坐标是否在网格范围内privatebooleaninArea(int x,int y){return x >=0&& x <N&& y >=0&& y <N;}// 并查集内部类privateclassUnionFind{privateint[] parent;// 父节点数组// 初始化并查集，每个节点的父节点初始化为自己publicUnionFind(int n){this.parent =newint[n];for(int i =0; i < n; i++){ parent[i]= i;}}// 查找根节点，并进行路径压缩优化publicintroot(int x){while(x != parent[x]){ parent[x]= parent[parent[x]];// 路径压缩 x = parent[x];}return x;}// 判断两个节点是否连通publicbooleanisConnected(int x,int y){returnroot(x)==root(y);// 通过比较根节点判断连通性}// 合并两个集合publicvoidunion(int p,int q){if(isConnected(p, q)){// 如果已经连通则直接返回return;} parent[root(p)]=root(q);// 将p的根节点连接到q的根节点下}}例题二
1.题目链接：省份数量
2.题目描述：
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
3.示例：
4.算法思路：
1 . 理解问题
省份：一组直接或间接相连的城市，组内不含其他没有相连的城市。
目标：统计这些省份的数量。
2 . 使用并查集
并查集是一种用于管理不相交集合的数据结构，特别适合处理动态连通性问题。它支持两个主要操作：
Find：确定某个元素属于哪个集合。
Union：将两个元素所在的集合合并。
在这个问题中，我们可以将每个城市视为一个元素，通过并查集来动态维护城市之间的连通性。
3 . 初始化并查集
创建一个并查集，包含 n 个城市。
初始时，每个城市是一个独立的集合，每个城市的父节点指向自己，秩为0。
4 . 遍历矩阵并合并城市
遍历矩阵 isConnected，对于每对直接相连的城市（isConnected[i][j] == 1），使用并查集的 union 操作将它们合并到同一个集合中。
通过 union 操作，我们可以动态地维护城市之间的连通性。
5 . 统计连通分量的数量
每次成功合并两个集合时，连通分量的数量减1。
最终，连通分量的数量即为省份的数量。
5.代码示例：
// 计算省份数量（连接分量数量）publicintfindCircleNum(int[][] isConnected){// 边界检查：如果矩阵为空，返回0if(isConnected ==null|| isConnected.length ==0){return0;}// 获取城市数量int n = isConnected.length;// 初始化并查集，每个城市初始为独立的省份UnionFind uf =newUnionFind(n);// 遍历邻接矩阵的每一行（每个城市）for(int i =0; i < n; i++){// 遍历邻接矩阵的每一列（与其他城市的连接情况）for(int j =0; j < n; j++){// 如果城市i和城市j直接相连if(isConnected[i][j]==1){// 将这两个城市合并到同一个省份中 uf.union(i, j);}}}// 返回最终的省份数量return uf.getCount();}// 并查集类，用于管理城市的连接关系classUnionFind{int root[];// 每个节点的父节点int rank[];// 每个节点的秩（树的高度）int count;// 当前连通分量的数量// 构造函数，初始化并查集UnionFind(int size){ root =newint[size];// 初始化父节点数组 rank =newint[size];// 初始化秩数组 count = size;// 初始时每个城市都是独立的省份// 初始化每个节点的父节点为自己，秩为1for(int i =0; i < size; i++){ root[i]= i;// 每个节点初始时是自己的根节点 rank[i]=1;// 每个节点初始秩为1}}// 查找节点的根节点（带路径压缩优化）intfind(int x){// 如果x是根节点，直接返回if(x == root[x]){return x;}// 路径压缩：将查找路径上的所有节点直接连接到根节点return root[x]=find(root[x]);}// 合并两个节点所在的集合voidunion(int x,int y){// 找到x和y的根节点int rootX =find(x);int rootY =find(y);// 如果两个节点不在同一集合中if(rootX != rootY){// 按秩合并：将较小的树合并到较大的树下if(rank[rootX]> rank[rootY]){// X的秩更大，将Y的根节点连接到X的根节点下 root[rootY]= rootX;}elseif(rank[rootX]< rank[rootY]){// Y的秩更大，将X的根节点连接到Y的根节点下 root[rootX]= rootY;}else{// 秩相等，任选一个作为根节点，并将其秩加1 root[rootY]= rootX; rank[rootX]+=1;}// 合并后连通分量数量减1 count--;}};// 获取当前连通分量的数量intgetCount(){return count;}}总结
以上就是本文全部内容，主要介绍了并查集这一数据结构及其相关常用方法，之后引用了两道例题带大家更加清楚的学习了并查集在具体算法中的应用。感谢各位能够看到最后，如有问题，欢迎各位大佬在评论区指正，希望大家可以有所收获！创作不易，希望大家多多支持！
