算法与数据结构---并查集（Union-Find）

并查集（Union-Find）是一种高效管理动态集合的数据结构，核心解决两个问题：「查询两个元素是否属于同一集合」和「合并两个集合」。它广泛应用于图论（如连通分量检测、最小生成树Kruskal算法）、社交网络（好友关系连通性）、集合分类等场景，其优化后的时间复杂度接近常数级，是算法面试中的高频考点。

一、并查集的核心概念

1. 基本定义

• 元素与集合：每个元素初始时属于一个独立的集合（仅包含自身），集合用「根节点」标识（根节点的父节点是自身）。
• 核心操作：
  1. find(x)：查询元素x所在集合的根节点（判断两个元素是否同集，只需比较根节点是否相同）。
  2. union(x, y)：将元素x和y所在的两个集合合并为一个集合。
  3. init(n)：初始化n个独立集合（父节点数组、秩/大小数组初始化）。
• 设计思想：用「树结构」表示集合（每个集合是一棵多叉树），根节点是集合的唯一标识，通过父节点指针串联所有元素。

二、朴素并查集实现（无优化）

1. 数据结构设计

用两个数组存储核心信息（C++中常用vector实现动态大小）：

• parent[]：parent[i]表示元素i的父节点，初始时parent[i] = i（自环为根）。

2. 核心操作实现

（1）初始化

#include<vector>usingnamespace std;classUnionFind{private: vector<int> parent;// 父节点数组public:// 初始化n个独立集合（元素编号0~n-1）UnionFind(int n){ parent.resize(n);for(int i =0; i < n;++i){ parent[i]= i;// 每个元素的父节点是自身}}};

（2）find操作（递归版）

递归查找根节点，直到找到parent[x] == x的节点：

intfind(int x){if(parent[x]!= x){// 不是根节点，递归查找父节点returnfind(parent[x]);}return x;// 返回根节点}

（3）union操作（朴素版）

找到两个元素的根节点，将其中一个根节点的父节点指向另一个根节点：

voidunite(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX != rootY){// 不同集合才合并 parent[rootY]= rootX;// 把rootY挂到rootX上}}

3. 朴素版本的问题

• find操作效率低：树可能退化为链表（如依次合并1→2→3→4→…），此时find(x)的时间复杂度为O(n)。
• union操作无策略：随机合并导致树的高度激增，进一步恶化查询效率。

例如，若合并顺序为unite(0,1)、unite(1,2)、unite(2,3)...，树会变成一条长链，查询末尾元素的根节点需遍历所有节点。

三、并查集的两大优化

为将时间复杂度优化到近似O(α(n))（α是阿克曼函数的反函数，n为元素个数时α(n)≤5，可视为常数），需实现以下两个优化：

1. 优化一：路径压缩（Path Compression）

原理

在find(x)查询时，将路径上所有节点的父节点直接指向根节点，扁平化树结构，减少后续查询的路径长度。

实现（循环版，避免递归栈溢出）

intfind(int x){// 找到根节点int root = x;while(parent[root]!= root){ root = parent[root];}// 路径压缩：将x到根节点的所有节点直接挂到根上while(parent[x]!= root){int next = parent[x];// 保存x的原父节点 parent[x]= root;// x直接指向根 x = next;// 处理下一个节点}return root;}

效果

一次find(x)后，后续查询该路径上的任何节点，都能直接找到根节点，查询效率大幅提升。

2. 优化二：按秩合并（Union by Rank）/ 按大小合并（Union by Size）

原理

合并两个集合时，让“矮树”挂到“高树”的根上（按秩合并）或“小树”挂到“大树”的根上（按大小合并），避免树的高度无意义增长。

• 秩（Rank）：表示树的高度上限（初始时每个节点的秩为1）。
• 大小（Size）：表示集合的元素个数（初始时每个集合的大小为1）。

实现（按秩合并）

需新增rank[]数组存储每个根节点的秩：

classUnionFind{private: vector<int> parent; vector<int> rank;// 秩数组：根节点的秩表示树的高度上限public:UnionFind(int n){ parent.resize(n); rank.resize(n,1);// 初始秩为1for(int i =0; i < n;++i){ parent[i]= i;}}// 带路径压缩的findintfind(int x){if(parent[x]!= x){ parent[x]=find(parent[x]);// 递归版路径压缩（简洁，适合n较小场景）}return parent[x];}// 按秩合并voidunite(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX == rootY)return;// 同集无需合并// 秩小的树挂到秩大的树上if(rank[rootX]< rank[rootY]){ parent[rootX]= rootY;}else{ parent[rootY]= rootX;// 若秩相等，合并后根的秩+1if(rank[rootX]== rank[rootY]){ rank[rootX]++;}}}};

实现（按大小合并）

需新增size[]数组存储每个集合的元素个数：

classUnionFind{private: vector<int> parent; vector<int> size;// 大小数组：根节点的size表示集合元素个数public:UnionFind(int n){ parent.resize(n); size.resize(n,1);// 初始大小为1for(int i =0; i < n;++i){ parent[i]= i;}}intfind(int x){// 循环版路径压缩（适合n较大，避免栈溢出）int root = x;while(parent[root]!= root) root = parent[root];while(parent[x]!= root){int next = parent[x]; parent[x]= root; x = next;}return root;}voidunite(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX == rootY)return;// 小数组合并到大树（减少高度增长）if(size[rootX]< size[rootY]){ parent[rootX]= rootY; size[rootY]+= size[rootX];// 更新大树的大小}else{ parent[rootY]= rootX; size[rootX]+= size[rootY];}}};

选择建议

• 按秩合并和按大小合并效果类似，均能保证树的高度不超过logn。
• 按大小合并更直观（可直接获取集合元素个数），按秩合并在某些场景（如带权并查集）更灵活。

四、并查集的核心功能扩展

除了基础的find和unite，实际应用中常需以下扩展功能：

1. 查询集合元素个数

基于按大小合并的size[]数组，查询元素x所在集合的大小：

intgetSize(int x){int root =find(x);return size[root];}

2. 判断两个元素是否连通

boolisConnected(int x,int y){returnfind(x)==find(y);}

3. 统计连通分量个数

遍历所有元素，统计根节点的数量（parent[i] == i的节点数）：

intcountComponents(){int cnt =0;for(int i =0; i < parent.size();++i){if(parent[i]== i){ cnt++;}}return cnt;}

五、并查集的经典应用场景（附C++示例）

场景1：无向图的环检测

问题描述

给定一个无向图，判断图中是否存在环。

原理

遍历所有边(u, v)：

• 若u和v已连通（find(u) == find(v)），则添加该边会形成环。
• 若未连通，则合并u和v所在集合。

C++实现

#include<vector>#include<iostream>usingnamespace std;classUnionFind{private: vector<int> parent; vector<int> size;public:UnionFind(int n){ parent.resize(n); size.resize(n,1);for(int i =0; i < n;++i) parent[i]= i;}intfind(int x){int root = x;while(parent[root]!= root) root = parent[root];while(parent[x]!= root){int next = parent[x]; parent[x]= root; x = next;}return root;}voidunite(int x,int y){int rootX =find(x), rootY =find(y);if(rootX == rootY)return;if(size[rootX]< size[rootY]){ parent[rootX]= rootY; size[rootY]+= size[rootX];}else{ parent[rootY]= rootX; size[rootX]+= size[rootY];}}boolisConnected(int x,int y){returnfind(x)==find(y);}};// 判断无向图是否有环（节点数n，边集edges）boolhasCycle(int n, vector<vector<int>>& edges){ UnionFind uf(n);for(auto& edge : edges){int u = edge[0], v = edge[1];if(uf.isConnected(u, v)){returntrue;// 存在环} uf.unite(u, v);}returnfalse;}intmain(){int n =5; vector<vector<int>> edges ={{0,1},{1,2},{2,3},{3,1}};// 存在环 cout <<"是否有环："<<(hasCycle(n, edges)?"是":"否")<< endl;// 输出：是return0;}

场景2：连通分量计数（岛屿数量变种）

问题描述

给定一个m×n的网格，1表示陆地，0表示水域，统计连通的陆地块数（上下左右为连通）。

原理

将每个陆地格子视为一个元素，编号为i×n + j（二维转一维），遍历每个陆地格子，与相邻陆地格子合并，最后统计连通分量个数。

C++实现

#include<vector>#include<iostream>usingnamespace std;classUnionFind{private: vector<int> parent; vector<int> size;int count;// 连通分量个数public:UnionFind(int n){ parent.resize(n); size.resize(n,1); count = n;// 初始每个元素是一个分量for(int i =0; i < n;++i) parent[i]= i;}intfind(int x){if(parent[x]!= x) parent[x]=find(parent[x]);return parent[x];}voidunite(int x,int y){int rootX =find(x), rootY =find(y);if(rootX == rootY)return;if(size[rootX]< size[rootY]){ parent[rootX]= rootY; size[rootY]+= size[rootX];}else{ parent[rootY]= rootX; size[rootX]+= size[rootY];} count--;// 合并后分量数-1}intgetCount(){return count;}};intnumIslands(vector<vector<char>>& grid){if(grid.empty()|| grid[0].empty())return0;int m = grid.size(), n = grid[0].size();int waterCount =0;// 水域数量（无需参与合并） UnionFind uf(m * n);// 方向数组：上下左右int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};for(int i =0; i < m;++i){for(int j =0; j < n;++j){if(grid[i][j]=='0'){ waterCount++;continue;}// 遍历相邻格子for(auto& dir : dirs){int x = i + dir[0], y = j + dir[1];if(x >=0&& x < m && y >=0&& y < n && grid[x][y]=='1'){int idx1 = i * n + j;int idx2 = x * n + y; uf.unite(idx1, idx2);}}}}// 总分量数 = 陆地分量数 = 总分量数 - 水域数return uf.getCount()- waterCount;}intmain(){ vector<vector<char>> grid ={{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}}; cout <<"岛屿数量："<<numIslands(grid)<< endl;// 输出：3return0;}

场景3：Kruskal算法求最小生成树

原理

Kruskal算法的核心是“选边不形成环”，利用并查集快速判断边的两个端点是否连通，优先选择权值最小的边合并，最终得到最小生成树。

六、带权并查集与扩展域并查集

1. 带权并查集（Weighted Union-Find）

核心思想

在parent[]基础上，新增weight[]数组，存储节点到父节点的权值（如距离、偏移量、关系系数）。find(x)时不仅压缩路径，还需更新权值（维护路径上的权值累加）；unite(x, y)时需根据已知关系计算根节点间的权值，确保权值一致性。

应用场景

• 维护节点间的相对关系（如“x比y大5”“x是y的前驱”）。
• 解决动态连通性中的权值传递问题（如LeetCode 399. 除法求值）。

C++简化示例（维护节点到根的距离）

classWeightedUnionFind{private: vector<int> parent; vector<int> weight;// weight[x]：x到parent[x]的距离public:WeightedUnionFind(int n){ parent.resize(n); weight.resize(n,0);// 初始时x到自身距离为0for(int i =0; i < n;++i) parent[i]= i;}intfind(int x){if(parent[x]!= x){int origParent = parent[x];// 保存原父节点 parent[x]=find(parent[x]);// 递归压缩路径（先找到根） weight[x]+= weight[origParent];// 更新x到根的距离（累加原父节点到根的距离）}return parent[x];}// 合并x和y，已知x到y的距离为d（即x = y + d）voidunite(int x,int y,int d){int rootX =find(x), rootY =find(y);if(rootX == rootY)return; parent[rootX]= rootY;// 计算rootX到rootY的距离：weight[x] + (rootX到rootY的距离) = d + weight[y] weight[rootX]= d + weight[y]- weight[x];}// 查询x到y的距离（若不连通返回-1）intgetDistance(int x,int y){if(find(x)!=find(y))return-1;return weight[x]- weight[y];}};

2. 扩展域并查集（Extended Union-Find）

核心思想

将每个元素的“状态”扩展为多个节点（如“x的朋友”“x的敌人”），通过合并扩展节点间接维护元素间的复杂关系（如“敌人的敌人是朋友”）。

应用场景

• 处理对立关系（如LeetCode 886. 可能的二分法）。
• 解决集合中的“黑白染色”问题。

核心思路

• 每个元素x拆分为两个节点：x（表示“x属于A组”）和x + n（表示“x属于B组”）。
• 若x和y是敌人，则合并x与y + n、x + n与y（x在A则y在B，x在B则y在A）。
• 若x和y是朋友，则合并x与y、x + n与y + n（x和y同组）。

七、时间复杂度与空间复杂度分析

1. 时间复杂度

• 朴素版：find和unite均为O(n)（树退化为链表）。
• 优化版（路径压缩+按秩/大小合并）：单次操作时间复杂度为O(α(n))，α是阿克曼函数的反函数，增长极慢（n≤1e6时α(n)=4），可视为O(1)。
• 带权/扩展域并查集：时间复杂度与优化版一致，仅增加常数级的权值计算/扩展节点操作。

2. 空间复杂度

• 基础版：O(n)（parent、rank/size数组）。
• 带权版：O(n)（新增weight数组）。
• 扩展域版：O(kn)（k为扩展状态数，如敌人/朋友场景k=2）。

注意事项

1. 核心要点

• 并查集的灵魂是「路径压缩」和「按秩/大小合并」，缺一不可，否则效率会急剧下降。
• 优先使用循环版find（避免递归栈溢出，尤其当n较大时）。
• 二维网格问题需将二维坐标转为一维编号（如i×n + j），方便并查集管理。

2. 常见误区

• 合并时直接操作元素x和y，而非它们的根节点（会导致合并失效）。
• 路径压缩时忘记更新带权并查集的权值（导致权值错误）。
• 扩展域并查集的状态拆分逻辑错误（如敌人关系合并方向颠倒）。

3. 适用场景总结

• 动态连通性查询（如好友关系、网络连通）。
• 集合合并与计数（如连通分量、岛屿数量）。
• 无向图环检测（如Kruskal算法）。
• 节点间关系维护（带权/扩展域并查集）。