并查集算法简介

前置知识：基本的数组操作、递归思想。

例题 on Luogu：

• P3367 【模板】并查集

并查集简介

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种操作：

• 查询（Find）：查询某个元素属于哪个集合
• 合并（Union）：将两个集合合并成一个集合

并查集在判断图连通性、最小生成树（Kruskal算法）等方面有广泛应用。

并查集结构

如图所示，并查集用一棵树来表示一个集合，树中的每个节点代表一个元素，根节点作为这个集合的代表。

初始时，每个元素自成一棵树，即每个元素都是自己的根节点。

我们可以用一个数组 fa 来存储每个节点的父节点：

• fa[i] 表示元素 i 的父节点
• 如果 fa[i] = i，则 i 是所在集合的根节点

初始化

一开始，每个元素都是独立的集合，所以每个元素的父节点都是自己。

void init(int n) { for(int i = 1; i <= n; i++) { fa[i] = i; } }

查询操作（Find）

查询操作的目标是找到元素所在集合的根节点。最简单的实现是沿着父节点一直向上找，直到找到根节点。

int find(int x) { while(fa[x] != x) // 不是根节点就继续向上 { x = fa[x]; } return x; }

或者使用递归写法：

int find(int x) { if(fa[x] == x) return x; return find(fa[x]); }

路径压缩优化

上面的查询操作在最坏情况下（树退化成链）时间复杂度为 O(n)。路径压缩可以在查询的同时，将路径上的所有节点直接指向根节点，从而优化后续查询。

int find(int x) { if(fa[x] != x) { fa[x] = find(fa[x]); // 路径压缩 } return fa[x]; }

经过路径压缩后，查询操作的时间复杂度接近 O(1)。

合并操作（Union）

合并操作将两个元素所在的集合合并成一个集合。基本思路是：先找到两个元素各自的根节点，然后将其中一个根节点的父节点指向另一个根节点。

void unionSet(int x, int y) { int rootX = find(x); int rootY = find(y);

if(rootX != rootY) // 不在同一个集合才需要合并
{
fa[rootX] = rootY; // 将rootX的父节点设为rootY
}

}

按秩合并优化

为了避免树的高度增长过快，可以引入"秩"的概念。秩通常表示树的高度或大小。合并时，将秩较小的树合并到秩较大的树上，这样能控制树的高度。

int rank[N]; // 秩数组，需要额外初始化（全部为1或0）

void init(int n) { for(int i = 1; i <= n; i++) { fa[i] = i; rank[i] = 1; // 初始秩为1 } }

void unionSet(int x, int y) { int rootX = find(x); int rootY = find(y);

if(rootX == rootY) return;

// 将秩小的树合并到秩大的树上
if(rank[rootX] < rank[rootY])
{
fa[rootX] = rootY;
}
else if(rank[rootX] > rank[rootY])
{
fa[rootY] = rootX;
}
else
{
fa[rootX] = rootY;
rank[rootY]++; // 两树秩相等，合并后秩加1
}

}

时间复杂度分析

• 只使用路径压缩：均摊时间复杂度 O(α(n))，α(n) 是阿克曼函数的反函数，增长极慢
• 只使用按秩合并：时间复杂度 O(log n)
• 路径压缩 + 按秩合并：均摊时间复杂度 O(α(n))，近乎常数时间

完整代码模板

#include<bits/stdc++.h> using namespace std;

const int N = 10005;

int fa[N]; int rank[N]; // 按秩合并用

// 初始化 void init(int n) { for(int i = 1; i <= n; i++) { fa[i] = i; rank[i] = 1; } }

// 查询（带路径压缩） int find(int x) { if(fa[x] != x) { fa[x] = find(fa[x]); } return fa[x]; }

// 合并（带按秩合并） void unionSet(int x, int y) { int rootX = find(x); int rootY = find(y);

if(rootX == rootY) return;

if(rank[rootX] < rank[rootY])
{
fa[rootX] = rootY;
}
else if(rank[rootX] > rank[rootY])
{
fa[rootY] = rootX;
}
else
{
fa[rootX] = rootY;
rank[rootY]++;
}

}

// 判断两个元素是否在同一集合 bool isSame(int x, int y) { return find(x) == find(y); }

int main() { int n, m; cin >> n >> m;

init(n);

while(m–)
{
int op, x, y;
cin >> op >> x >> y;

if(op == 1) // 合并操作
{
unionSet(x, y);
}
else // 查询操作
{
if(isSame(x, y))
{
cout << "Y" << endl;
}
else
{
cout << "N" << endl;
}
}
}

return 0;

}

并查集的应用

1. 判断图的连通性

可以用并查集维护图中各连通分量，快速判断两个点是否连通。

2. Kruskal最小生成树

按边权从小到大排序，依次尝试加入边，如果边的两端不在同一集合，则加入该边并合并两端点。

int kruskal() { int ans = 0, cnt = 0; sort(edges + 1, edges + m + 1, cmp); // 按边权排序

for(int i = 1; i <= m; i++)
{
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
if(!isSame(u, v))
{
unionSet(u, v);
ans += w;
cnt++;
if(cnt == n – 1) break;
}
}

if(cnt == n – 1) return ans;
else return -1; // 图不连通

}

3. 求连通块个数

遍历所有节点，统计根节点的个数即可。

int countComponents(int n) { int cnt = 0; for(int i = 1; i <= n; i++) { if(find(i) == i) cnt++; } return cnt; }

4. 带权并查集（扩展域）

在维护集合关系的同时，还可以维护节点与根节点之间的某种关系（如距离、种类等），这就是带权并查集。

常见技巧与注意事项

int rootX = find(x); int rootY = find(y); // 后续使用 rootX 和 rootY 而不是重复调用 find

恭喜你初步学会了并查集，可以去推荐题目中试试哦！