- 刷 NBUOJ 遇到的，一直没来得及记录
- 整点数据结构
- 记录一下模板
概念
Disjoint Set 的原意是指不相交的集合，即两集合的交集为空集
具体实现实际上是将某元素所属集合与另一元素所属集合合并，并且可以用来快速判断两元素是否子同属一个集合
也可以认为是通过路径压缩，使元素要么为树的根节点，要么为根节点的叶节点
基本操作
顾名思义，支持两种操作合并，查询
- 合并（Merge/Union）：将两元素所属的集合合并
- 查询（Find）：查询某个元素所属集合
实现
非路径压缩版本1
2
3
4
5
6
7
8
9
10
11
12
| class DisjointSet {
private:
vector<int> arr;
public:
DisjointSet() = default;
DisjointSet(const vector<int>::size_type s) : arr(s) {
iota(arr.begin(), arr.end(), 0);
}
int find(int x) { return arr[x] == x ? x : find(arr[x]); }
void merge(int a, int b) { arr[find(b)] = arr[find(a)]; }
};
|
路径压缩版本1
2
3
4
5
6
7
8
9
10
11
12
| class DisjointSet {
private:
vector<int> arr;
public:
DisjointSet() = default;
DisjointSet(const vector<int>::size_type s) : arr(s) {
iota(arr.begin(), arr.end(), 0);
}
int find(int x) { return arr[x] = arr[x] == x ? x : find(arr[x]); }
void merge(int a, int b) { arr[find(b)] = arr[find(a)]; }
};
|
其实差异只有 find 的实现
1
2
| - int find(int x) { return arr[x] == x ? x : find(arr[x]); }
+ int find(int x) { return arr[x] = arr[x] == x ? x : find(arr[x]); }
|
复杂度分析
参考：oi-wiki
- 对于每个操作：在路径压缩后的时间复杂度为 为 Ackerman
函数，其增长极为缓慢，近似可认为是常数时间
例题
题目描述
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x,y
是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。
输入描述
输入有多组测试数据
每组测试数组输入：
第一行：三个整数 ，，分别表示有
个人， 个亲戚关系，询问 对亲戚关系。
以下 行：每行两个数 ，表示 和 具有亲戚关系。
接下来 行：每行两个数 ，询问 和 是否具有亲戚关系。
输出描述
行，每行一个
'Yes' 或 'No'。
表示第
个询问的答案为“具有”或“不具有”亲戚关系。
示例
输入1
2
3
4
5
6
7
8
9
| 6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
|
输出
Solution
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
| #include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
class DisjointSet {
private:
vector<int> arr;
public:
DisjointSet() = default;
DisjointSet(const vector<int>::size_type s) : arr(s) {
iota(arr.begin(), arr.end(), 0);
}
int find(int x) { return arr[x] = arr[x] == x ? x : find(arr[x]); }
void merge(int a, int b) { arr[find(b)] = arr[find(a)]; }
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, p;
int i, j;
cin >> n >> m >> p;
DisjointSet dsu(n + 1);
while (m--) {
cin >> i >> j;
dsu.merge(i, j);
}
while (p--) {
cin >> i >> j;
if (dsu.find(i) == dsu.find(j))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
|