并查集
发布于2020-12-05
上次编辑2021-04-20
Introduction
并查集是用于处理 不相交集合 的 查询 与 合并 问题的数据结构。它包含三种基本操作：
- 集合初始化
- 查询元素所在集合
-
合并两个集合
-
LeetCode 并查集专题
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 | class UnionFind:
def __init__(self):
self.fa = None
self.size = None
def init_set(self, n: int) -> None:
self.fa = list(range(n))
self.size = [1] * n
def find_set(self, x: int) -> int:
if x != self.fa[x]:
self.fa[x] = self.find_set(self.fa[x])
return self.fa[x]
def union_sets(self, x: int, y: int) -> bool:
x, y = self.find_set(x), self.find_set(y)
if x == y: return False
if self.size[x] < self.size[y]: x, y = y, x
self.fa[y] = x
self.size[x] += self.size[y]
return True
def is_connected(self, x: int, y: int) -> bool:
return self.find_set(x) == self.find_set(y)
def count(self) -> int:
return sum(1 for i, x in enumerate(self.fa) if i == x)
|
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 | class UnionFind {
public:
vector<int> fa, size;
void init_set(int n) {
fa.resize(n), size.resize(n);
for (int i = 0; i < n; ++i) { fa[i] = i, size[i] = 1; }
}
int find_set(int x) { return x == fa[x] ? x : (fa[x] = find_set(fa[x])); }
bool union_sets(int x, int y) {
x = find_set(x), y = find_set(y);
if (x == y) return false;
if (size[x] < size[y]) swap(x, y);
fa[y] = x, size[x] += size[y];
return true;
}
bool is_connected(int x, int y) { return find_set(x) == find_set(y); }
int count() {
int n = fa.size(), cnt = 0;
for (int i = 0; i < n; ++i) if (i == fa[i]) ++cnt;
return cnt;
}
};
|