简介
英文:Disjoint Set,即“不相交集合”。将编号分别为1…N的N个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。常见两种操作:
- 合并两个集合;
- 查找某元素属于哪个集合。
代码
1 无优化
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
| const int maxn = 1e5; int node[maxn];
void init(int n) { for( int i=0; i<=n; i++ ){ node[i] = i; } }
int find(int x) { if (x == node[x]) return x; return find(node[x]); }
void merge(int x, int y) { int root_x = find(x); int root_y = find(y); if (root_x == root_y) return ; node[root_x] = root_y; }
bool same(int x, int y) { return find(x) == find(y); }
|
2 优化(路径压缩+按秩合并)
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
| const int maxn = 1e5; int node[maxn]; int Rank[maxn];
void init(int n) { for (int i=0; i<=n; i++) { node[i] = i; Rank[i] = 1; } }
int find(int x) { if (x == node[x]) return x; return node[x] = find(node[x]); }
void merge(int x, int y) { int root_x = find(x); int root_y = find(y); if (root_x == root_y) return ; if (Rank[root_x] < Rank[root_y]) node[root_x] = root_y; else { node[root_y] = root_x; if (Rank[root_x] == Rank[root_y]) Rank[root_x]++; } }
bool same(int x, int y) { return find(x) == find(y); }
|
时间复杂度
直接实现的话,时间复杂度最坏可以到O(n)。 两个常见优化,启发式合并,路径压缩。
- 启发式合并:把大小较小的集合挂在较大的集合上。(有的写法是考虑深度而不是大小)
- 路径压缩:询问过的点到根节点的路径,都直接挂在根节点上。
实现其中任意一个时间复杂度变为O(\log n)。 实现其中两个,时间复杂度变为O(\alpha(n)),其中\alpha(n)是阿克曼函数的反函数,可以认为非常小。
多数情况下为了简单,都实现路径压缩(只需要一句赋值)而不实现启发式合并(需要记录大小)
在某些题目中由于会爆栈,需要使用非递归的find函数。
练习
- 洛谷——P3367 【模板】并查集