forked from gzc/CLRS
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathuf.cpp
77 lines (64 loc) · 1.53 KB
/
uf.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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
using namespace std;
class UF {
private:
int *parent;
int *rank;
int count;
int N;
bool validate(int p) {
return ( p > 0 && p <= N);
}
public:
UF(int N) {
parent = new int[N];
rank = new int[N];
this->N = N;
count = N;
for(int i = 0;i < N;i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int p) {
if(!validate(p)) return -1;
while (p != parent[p]) {
parent[p] = parent[parent[p]]; // path compression by halving
p = parent[p];
}
return p;
}
int getCount() {
return count;
}
bool connected(int p, int q) {
return find(p) == find(q);
}
void Union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// make root of smaller rank point to root of larger rank
if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
~UF() {
delete []parent;
delete []rank;
}
};
int main() {
UF uf(5);
cout << uf.getCount() << endl;
cout << uf.connected(2, 4) << endl;
uf.Union(1, 2);
uf.Union(3, 4);
cout << uf.getCount() << endl;
uf.Union(1, 3);
cout << uf.connected(2, 4) << endl;
}