|
athos@250
|
1 |
// -*- C++ -*- //
|
|
athos@250
|
2 |
/*
|
|
athos@250
|
3 |
Union-Find structure
|
|
athos@250
|
4 |
|
|
athos@250
|
5 |
* Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
|
|
athos@250
|
6 |
* minden szobajovo kulcs ertekre, -1 -es ertekkel!
|
|
athos@250
|
7 |
|
|
athos@250
|
8 |
*/
|
|
athos@250
|
9 |
#ifndef UNION_FIND_H
|
|
athos@250
|
10 |
#define UNION_FIND_H
|
|
athos@250
|
11 |
|
|
athos@250
|
12 |
#include <vector>
|
|
athos@250
|
13 |
//#include <map>
|
|
athos@250
|
14 |
|
|
athos@250
|
15 |
|
|
alpar@921
|
16 |
namespace lemon {
|
|
athos@250
|
17 |
|
|
athos@250
|
18 |
template <typename KeyType, typename KeyIntMap>
|
|
athos@250
|
19 |
class UnionFind {
|
|
athos@250
|
20 |
KeyIntMap& pointmap;
|
|
athos@250
|
21 |
struct VectorElementType {
|
|
athos@250
|
22 |
int boss;
|
|
athos@250
|
23 |
int count;
|
|
athos@250
|
24 |
VectorElementType(int _boss, int _count){
|
|
athos@250
|
25 |
boss = _boss;
|
|
athos@250
|
26 |
count = _count;
|
|
athos@250
|
27 |
}
|
|
athos@250
|
28 |
};
|
|
athos@250
|
29 |
std::vector<VectorElementType> container;
|
|
athos@250
|
30 |
public:
|
|
athos@250
|
31 |
|
|
athos@250
|
32 |
UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){
|
|
athos@250
|
33 |
|
|
athos@250
|
34 |
}
|
|
athos@250
|
35 |
|
|
athos@250
|
36 |
//Give a component of one point to the structure
|
|
athos@250
|
37 |
int addPoint(KeyType u){
|
|
athos@250
|
38 |
int _index = container.size();
|
|
athos@250
|
39 |
VectorElementType buf(_index,1);
|
|
athos@250
|
40 |
container.push_back(buf);
|
|
athos@250
|
41 |
return _index;
|
|
athos@250
|
42 |
}
|
|
athos@250
|
43 |
|
|
athos@250
|
44 |
|
|
athos@250
|
45 |
//Finds the big boss of u
|
|
athos@250
|
46 |
int find(KeyType u){
|
|
athos@250
|
47 |
if (pointmap.get(u)==-1){
|
|
athos@250
|
48 |
int whoami = addPoint(u);
|
|
athos@250
|
49 |
pointmap.set(u, whoami);
|
|
athos@250
|
50 |
return whoami;
|
|
athos@250
|
51 |
}
|
|
athos@250
|
52 |
else{
|
|
athos@250
|
53 |
int emp = pointmap.get(u);
|
|
athos@250
|
54 |
int boss = container[emp].boss;
|
|
athos@250
|
55 |
while(emp != boss){
|
|
athos@250
|
56 |
emp = boss;
|
|
athos@250
|
57 |
boss = container[emp].boss;
|
|
athos@250
|
58 |
}
|
|
athos@250
|
59 |
return boss;
|
|
athos@250
|
60 |
}
|
|
athos@250
|
61 |
}
|
|
athos@250
|
62 |
|
|
athos@250
|
63 |
//Finds u and v in the structures and merges the comopnents, if not equal
|
|
athos@250
|
64 |
bool findAndMerge(KeyType u,KeyType v){
|
|
athos@250
|
65 |
int bu = find(u);
|
|
athos@250
|
66 |
int bv = find(v);
|
|
athos@250
|
67 |
if (bu != bv){
|
|
athos@250
|
68 |
unio(bu,bv);
|
|
athos@250
|
69 |
return true;
|
|
athos@250
|
70 |
}
|
|
athos@250
|
71 |
else{
|
|
athos@250
|
72 |
return false;
|
|
athos@250
|
73 |
}
|
|
athos@250
|
74 |
}
|
|
athos@250
|
75 |
|
|
athos@250
|
76 |
//Merges a into b
|
|
athos@250
|
77 |
void mergeInto(int a, int b){
|
|
athos@250
|
78 |
container[a].boss = b;
|
|
athos@250
|
79 |
container[b].count += container[a].count;
|
|
athos@250
|
80 |
}
|
|
athos@250
|
81 |
|
|
athos@250
|
82 |
//Makes the union
|
|
athos@250
|
83 |
void unio(int b1, int b2){
|
|
athos@250
|
84 |
if (container[b1].count>container[b2].count){
|
|
athos@250
|
85 |
mergeInto(b2,b1);
|
|
athos@250
|
86 |
}
|
|
athos@250
|
87 |
else{
|
|
athos@250
|
88 |
mergeInto(b1,b2);
|
|
athos@250
|
89 |
}
|
|
athos@250
|
90 |
}//unio
|
|
athos@250
|
91 |
};
|
|
athos@250
|
92 |
|
|
alpar@921
|
93 |
}//namespace lemon
|
|
athos@250
|
94 |
#endif
|