并查集
概述
- 并查集是一种树形数据结构，经常用于处理一些集合之间的操作，例如元素查找，集合合并。
- 不同集合在并查集中以不同的树表示，一般每棵树的根节点会作为当前集合的代表元。
- 想要查询两个元素是不是在同一集合中，只需要比较两个元素所在集合的代表元是否相同即可。
实现
-
初始化
-
const int N = 100010; int fa[N];//记录每个元素由谁代表 int sz[N];//记录每个集合元素个数 int dep[N + 1];//记录每个集合树的深度 -
假设有 \(n\) 个元素，这些元素初始都是独立的。显然它们构成了 \(n\) 个集合，每个集合的代表元就是元素自己。
-
void initalize(int n) { for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = dep[i] = 1; } } -
将两个元素 \(x\)，\(y\) 所在的集合合并。
-
先找到 \(x\)，\(y\) 对应的代表元。（即 \(\text{fa}\) 等于自己的元素）
-
将其中一个代表元的 \(\text{fa}\) 指向另外一个，那么在这个代表元下的所有元素都会指向另外一个。
-
int findSet(int x) { if (fa[x] == x) { return x; } return findSet(fa[x]); } void Union(int x, int y) { int fx = findSet(x), fy = findSet(y); if (fx == fy) { return ; } fa[fx] = fy;//把fx的代表元改为fy }
-
-
路径压缩
-
如果并查集在合并中形成一条长链，每次查找代表元都可能要花费大量时间。
-
我们可以缩短并查集中的路径，具体做法就是在查询的过程中，把沿途的每个节点的 \(\text{fa}\) 都设为集合代表元。
-
当有 \(n\) 个元素和 \(m\) 次查询时，时间复杂度 \(\operatorname O(m\log n)\)
-
1 1 | / | \ 2 2 3 4 | 3 | 4
-
-
int findSet(int x) { if (x == fa[x]) { return x; } fa[x] = findSet(fa[x]);//路径压缩 return fa[x]; } -
//简写 int findSet(int x) { return x == fa[x] ? x : (fa[x] = findSet(fa[i])); }
-
-
启发式合并
-
在合并集合的时候，我们尽量选择包含元素个数少的集合把它并入另一个集合中，使需要改变代表元的元素的数量尽可能少。
-
当有 \(n\) 个元素和 \(m\) 次查询时，时间复杂度 \(\operatorname O(m\log n)\)（跟路径压缩没差，其实可以用路径压缩）
-
void Union(int x, int y) { int fx = findSet(x), fy = findSet(y); if (fx == fy) { return ; } if (sz[fx] > sz[fy]) { swap(fx, fy); } fa[fx] = fy; sz[fy] += sz[fx]; }
-
-
按深度合并
-
在合并集合的时候，我们尽量选择深度较小的集合把它并入另一个集合中。
-
在路径压缩的时候，有可能会破坏维护的深度值，但算法总体复杂度不会变差
-
void Union(int x, int y) { int fx = findSet(x), fy = findSet(y); if (fx == fy) return; if (dep[fx] > dep[fy]) swap(fx, fy); fa[fx] = fy; if (dep[fx] == dep[fy]) dep[fy]++; }
-
例题
-
-
模板题
-
#include<iostream> #include<algorithm> #include<cstdio> const int N = 5e3 + 10; int n, m, p; int fa[N]; int findSet(int x); void Union(int x, int y) { int fx = findSet(x), fy = findSet(y); if (fx == fy) return; fa[fx] = fy; } int findSet(int x) { if (x == fa[x]) { return x; } fa[x] = findSet(fa[x]); return fa[x]; } void initalize(int n) { for (int i = 1; i <= n; i++) { fa[i] = i; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::cin >> n >> m >> p; initalize(n); for (int i = 1; i <= m; i++) { int x, y; std::cin >> x >> y; Union(x, y); } for (int i = 1; i <= p; i++) { int x, y; std::cin >> x >> y; if (findSet(x) == findSet(y)) { std::cout << "Yes\n"; } else { std::cout << "No\n"; } } return 0; }
-
-
统计连通块
-
这类题统计连通块个数就是统计 \(fa\) 数组等于其本身的个数。
-
即集合数量。
-
#include<iostream> #include<algorithm> #include<cstdio> int fa[1000010]; int m, n; int vis[1000010]; int ans; int findSet(int x) { if (x == fa[x]) { return x; } fa[x] = findSet(fa[x]); return fa[x]; } void Union(int x, int y) { int fx = findSet(x), fy = findSet(y); if (fx == fy) { return ; } fa[fx] = fy; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::cin >> m >> n; int k; std::cin >> k; for (int i = 1; i <= n * m; i++) { fa[i] = i; } for (int i = 1; i <= k; i++) { int a, b; std::cin >> a >> b; Union(a, b); } for (int i = 1; i <= n * m; i++) { if (fa[i] == i) ans++; } std::cout << ans; return 0; } -
#include<iostream> #include<algorithm> #include<cstdio> int n, m; int fa[1010]; void initalize(int n) { for (int i = 1; i <= n; i++) { fa[i] = i; } } int findSet(int x) { if (fa[x] == x) { return x; } fa[x] = findSet(fa[x]); return fa[x]; } void merge(int x, int y) { int fx = findSet(x), fy = findSet(y); if (fx == fy) return; fa[fx] = fy; return ; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); while(std::cin >> n >> m) { if (!n) break; initalize(n); while(m--) { int x, y; std::cin >> x >> y; merge(x, y); } int cnt = 0; for (int i = 1; i <= n; i++) { if (fa[i] == i) { cnt++; } } std::cout << cnt - 1 << std::endl; } return 0; }
-