介绍并查集（Union-Find）数据结构，涵盖核心概念、基础实现及路径压缩、按秩合并两大优化。内容包含 C++ 代码示例，讲解初始化、查找、合并操作，以及带权并查集和扩展域并查集的扩展应用。通过无向图环检测、岛屿数量统计、Kruskal 最小生成树等经典场景展示其用途，并分析时间与空间复杂度。
并查集（Union-Find）是一种高效管理动态集合的数据结构，核心解决两个问题：「查询两个元素是否属于同一集合」和「合并两个集合」。它广泛应用于图论（如连通分量检测、最小生成树 Kruskal 算法）、社交网络（好友关系连通性）、集合分类等场景，其优化后的时间复杂度接近常数级，是算法面试中的高频考点。
find(x)：查询元素x所在集合的根节点（判断两个元素是否同集，只需比较根节点是否相同）。union(x, y)：将元素x和y所在的两个集合合并为一个集合。init(n)：初始化n个独立集合（父节点数组、秩/大小数组初始化）。用两个数组存储核心信息（C++中常用vector实现动态大小）：
parent[]：parent[i]表示元素i的父节点，初始时parent[i] = i（自环为根）。#include <vector>
using namespace std;
class UnionFind {
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; // 每个元素的父节点是自身
}
}
};
递归查找根节点，直到找到parent[x] == x的节点：
int find(int x) {
if (parent[x] != x) { // 不是根节点，递归查找父节点
return find(parent[x]);
}
return x; // 返回根节点
}
找到两个元素的根节点，将其中一个根节点的父节点指向另一个根节点：
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) { // 不同集合才合并
parent[rootY] = rootX; // 把 rootY 挂到 rootX 上
}
}
find(x)的时间复杂度为O(n)。例如，若合并顺序为unite(0,1)、unite(1,2)、unite(2,3)...，树会变成一条长链，查询末尾元素的根节点需遍历所有节点。
为将时间复杂度优化到近似O(α(n))（α是阿克曼函数的反函数，n为元素个数时α(n)≤5，可视为常数），需实现以下两个优化：
在find(x)查询时，将路径上所有节点的父节点直接指向根节点，扁平化树结构，减少后续查询的路径长度。
int find(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)后，后续查询该路径上的任何节点，都能直接找到根节点，查询效率大幅提升。
合并两个集合时，让'矮树'挂到'高树'的根上（按秩合并）或'小树'挂到'大树'的根上（按大小合并），避免树的高度无意义增长。
需新增rank[]数组存储每个根节点的秩：
class UnionFind {
private:
vector<int> parent;
vector<int> rank; // 秩数组：根节点的秩表示树的高度上限
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n, 1); // 初始秩为 1
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
// 带路径压缩的 find
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 递归版路径压缩（简洁，适合 n 较小场景）
}
return parent[x];
}
// 按秩合并
void unite(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; // 若秩相等，合并后根的秩 +1
if (rank[rootX] == rank[rootY]) {
rank[rootX]++;
}
}
}
};
需新增size[]数组存储每个集合的元素个数：
class UnionFind {
private:
vector<int> parent;
vector<int> size; // 大小数组：根节点的 size 表示集合元素个数
public:
UnionFind(int n) {
parent.resize(n);
size.resize(n, 1); // 初始大小为 1
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(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;
}
void unite(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];
}
}
};
logn。除了基础的find和unite，实际应用中常需以下扩展功能：
基于按大小合并的size[]数组，查询元素x所在集合的大小：
int getSize(int x) {
int root = find(x);
return size[root];
}
bool isConnected(int x, int y) {
return find(x) == find(y);
}
遍历所有元素，统计根节点的数量（parent[i] == i的节点数）：
int countComponents() {
int cnt = 0;
for (int i = 0; i < parent.size(); ++i) {
if (parent[i] == i) {
cnt++;
}
}
return cnt;
}
给定一个无向图，判断图中是否存在环。
遍历所有边(u, v)：
u和v已连通（find(u) == find(v)），则添加该边会形成环。u和v所在集合。#include <vector>
#include <iostream>
using namespace std;
class UnionFind {
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;
}
int find(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;
}
void unite(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];
}
}
bool isConnected(int x, int y) {
return find(x) == find(y);
}
};
// 判断无向图是否有环（节点数 n，边集 edges）
bool hasCycle(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)) {
return true; // 存在环
}
uf.unite(u, v);
}
return false;
}
int main() {
int n = 5;
vector<vector<int>> edges = {{0,1}, {1,2}, {2,3}, {3,1}}; // 存在环
cout << "是否有环：" << (hasCycle(n, edges) ? "是" : "否") << endl; // 输出：是
return 0;
}
给定一个m×n的网格，1 表示陆地，0 表示水域，统计连通的陆地块数（上下左右为连通）。
将每个陆地格子视为一个元素，编号为i×n + j（二维转一维），遍历每个陆地格子，与相邻陆地格子合并，最后统计连通分量个数。
#include <vector>
#include <iostream>
using namespace std;
class UnionFind {
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;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(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
}
int getCount() {
return count;
}
};
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
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;
}
int main() {
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; // 输出：3
return 0;
}
Kruskal 算法的核心是'选边不形成环'，利用并查集快速判断边的两个端点是否连通，优先选择权值最小的边合并，最终得到最小生成树。
在parent[]基础上，新增weight[]数组，存储节点到父节点的权值（如距离、偏移量、关系系数）。find(x)时不仅压缩路径，还需更新权值（维护路径上的权值累加）；unite(x, y)时需根据已知关系计算根节点间的权值，确保权值一致性。
class WeightedUnionFind {
private:
vector<int> parent;
vector<int> weight; // weight[x]：x 到 parent[x] 的距离
public:
WeightedUnionFind(int n) {
parent.resize(n);
weight.resize(n, 0); // 初始时 x 到自身距离为 0
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(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）
void unite(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）
int getDistance(int x, int y) {
if (find(x) != find(y)) return -1;
return weight[x] - weight[y];
}
};
将每个元素的'状态'扩展为多个节点（如'x 的朋友''x 的敌人'），通过合并扩展节点间接维护元素间的复杂关系（如'敌人的敌人是朋友'）。
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 同组）。find和unite均为O(n)（树退化为链表）。O(α(n))，α是阿克曼函数的反函数，增长极慢（n≤1e6时α(n)=4），可视为O(1)。O(n)（parent、rank/size数组）。O(n)（新增weight数组）。O(kn)（k为扩展状态数，如敌人/朋友场景k=2）。find（避免递归栈溢出，尤其当n较大时）。i×n + j），方便并查集管理。x和y，而非它们的根节点（会导致合并失效）。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online