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