并查集-上
1. 并查集是什么
并查集（Disjoint Set Union，简称 DSU）是一种树型数据结构，专门用来高效地维护「元素分组」与「合并集合」两类操作：
find(u)：查询元素 u 所在集合的代表元（根）。merge(u, v)：把 u 与 v 所在集合合并成一个。
并查集的核心思想只有一句话：
用一棵树表示一个集合，树根就是集合的代表元，所有节点都指向根即可。
2. 朴素数组实现（TLE 版）
1
2
3
4
| int fa[N];
void init(int n) { for (int i = 0; i < n; ++i) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
|
- 时间复杂度：单次
find 最坏 $O(n)$，退化成链。
- 实战里几乎不用，仅作教学。
3. 路径压缩 + 按秩合并（左程云模板）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| struct DSU {
vector<int> fa, sz; // fa记录祖先,sz记录大小
DSU(int n) : fa(n), sz(n, 1) {
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]); // 路径压缩
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (sz[x] < sz[y]) swap(x, y); // 按秩合并
fa[y] = x;
sz[x] += sz[y];
return true;
}
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return sz[find(x)]; }
};
|
- 复杂度：单次操作均摊 $O(\alpha(n))$，其中 $\alpha(n)$ 为反阿克曼函数，可视为常数。
3.1 最小可用模板（仅保留路径压缩）
实际做题时，按秩合并不是刚需；只写路径压缩已能跑过绝大多数数据。
1
2
3
4
5
6
7
| struct DSU {
vector<int> fa;
DSU(int n) : fa(n) { for(int i = 0; i < n; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) { fa[find(x)] = find(y); }
};
|
fa[i] = i：初始化时每个人都认自己当老大。find：一边找根，一边顺手把路上所有人直接挂在根上——这就是路径压缩。merge：把两棵树的根随便粘在一起即可，树高靠路径压缩兜底，均摊仍是近乎常数。
注：如需严格保证最坏 $O(\alpha(n))$，再把 sz 和“按秩合并”加回来即可。
4. 经典例题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| struct DSU {
vector<int> fa;
DSU(int n) : fa(n) {
for (int i = 0; i < n; i++)
fa[i] = i;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
bool same(int x, int y) { return find(x) == find(y); }
};
int minSwapsCouples(vector<int> &row) {
int n = row.size();
int m = n / 2;
DSU dsu(m);
for (int i = 0; i < n; i += 2) {
dsu.merge(row[i] / 2, row[i + 1] / 2);
}
set<int> totaldsu;
for (int i = 0; i < m; i++) {
totaldsu.insert(dsu.find(i));
}
int ans = m - totaldsu.size(); // 总情侣对数-集合数量
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| struct DSU {
int sets; // 集合个数
vector<int> fa, sz;
DSU(int n) : fa(n), sz(n, 1) {
for (int i = 0; i < n; i++)
fa[i] = i;
sets = n;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { // 只有合并才sets--
int fx = find(x);
int fy = find(y);
if (fx != fy) {
fa[fx] = fy;
sets--;
}
}
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return sz[find(x)]; }
};
bool check(string &a, string &b) {
int n = a.size();
int diff = 0;
for (int i = 0; i < n && diff < 3; i++) {
if (a[i] != b[i]) {
diff++;
}
}
if (diff == 0 || diff == 2) {
return true;
}
return false;
}
int numSimilarGroups(vector<string> &strs) {
int n = strs.size();
int m = strs[0].size();
DSU dsu(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (check(strs[i], strs[j])) {
dsu.merge(i, j); // 只有merge后才sets--
}
}
}
return dsu.sets;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| struct DSU {
vector<int> fa;
int sets;
DSU(int n) : fa(n) {
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
fa[x] = y;
return true;
}
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int numIslands(vector<vector<char>> &grid) {
int ans = 0;
int n = grid.size();
int m = grid[0].size();
DSU dsu(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
dsu.sets++;
if (j > 0 && grid[i][j - 1] == '1') {
if (dsu.merge(i * m + j, i * m + j - 1))
dsu.sets--;
}
if (i > 0 && grid[i - 1][j] == '1') {
if (dsu.merge(i * m + j, (i - 1) * m + j))
dsu.sets--;
}
}
}
}
return dsu.sets;
}
|
5. 常见坑点与调试技巧
| 坑点 |
解决 |
忘记 init |
构造函数里统一初始化 |
| 多组数据没清空 |
每轮 fa.assign(n, iota) |
| 数组开小 |
把 N 设成 2e5 + 10 |
| 路径压缩写错 |
必须 fa[x] = find(fa[x]) |
调试时输出每个节点的根，观察是否出现「森林」。
