Disjoint Set (並查集)

路徑壓縮

Code












constexpr int N = 2e5 + 1;
int p[N];
void init(int n) {
	for (int i = 0; i <= n; i++) p[i] = i;
}
int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]);
}
void joint(int x, int y) {
	p[find(x)] = find(y);
}

啟發式合併

Code















constexpr int N = 2e5 + 1;
int p[N], s[N];
void init(int n) {
	for (int i = 0; i <= n; i++) p[i] = i, r[i] = 1;
}
int find(int x) {
	return p[x] == x ? x : find(p[x]);
}
void joint(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (s[x] > s[y]) s[x] += s[y], p[y] = x;
	else s[y] += s[x], p[x] = y;
}

路徑壓縮 + 啟發式合併

複雜度

建構(初始化) : \(O(N)\)
查詢 : \(O(\alpha(N))\)
合併 : \(O(\alpha(N))\)

Code

如上兩個一起使用而已。

Select a repo