A generic template.
1. Introduction
The algorithm has two main functions:
find: find a root parent given a node.union: merge a smaller set to a larger one if they are disjoint.
2. Template
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
| template<typename T>
class UnionFindSet {
public:
UnionFindSet(T n) {
_parents = std::vector<T>(n, 0);
_ranks = std::vector<T>(n, 0);
for (size_t i = 0; i < n; ++i)
_parents[i] = i;
}
bool unite(T u, T v) {
T pu = find(u);
T pv = find(v);
if (pu == pv) return false;
if (_ranks[pu] > _ranks[pv]) {
_parents[pv] = pu;
} else if (_ranks[pv] > _ranks[pu]) {
_parents[pu] = pv;
} else {
_parents[pu] = pv;
++_ranks[pv];
}
return true;
}
int find(T id) {
if (id != _parents[id])
_parents[id] = find(_parents[id]);
return _parents[id];
}
private:
std::vector<T> _parents;
std::vector<T> _ranks;
};
|
