-
Notifications
You must be signed in to change notification settings - Fork 5
/
001_UnionFind.cpp
61 lines (48 loc) · 1.07 KB
/
001_UnionFind.cpp
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <unordered_map>
#include <vector>
#include <assert.h>
#include <iostream>
using namespace std;
template<typename T>
class UnionFind{
public:
UnionFind(vector<T> nodes) {
for(T x : nodes) {
mp.insert({x, x});
}
}
T find(T x){
assert(mp.find(x) != mp.end());
if(mp[x] == x) {
return x;
}
T f = find(mp[x]);
mp[x] = f;
return f;
}
void unite(T x, T y) {
assert(mp.find(x) != mp.end());
assert(mp.find(y) != mp.end());
T f_x = find(x);
T f_y = find(y);
if(f_x != f_y) {
mp[f_x] = f_y;
}
}
bool isSame(T x, T y){
assert(mp.find(x) != mp.end());
assert(mp.find(y) != mp.end());
return mp[x] == mp[y];
}
private:
unordered_map<T, T> mp;
};
int main(){
vector<int> nums{1,2,3,4,5,6};
UnionFind<int> uf(nums);
uf.unite(1, 2); uf.unite(1, 3);
uf.unite(4, 5); uf.unite(5, 6);
for(int x : nums){
cout << x << ": " << uf.find(x) << endl;
}
}