equal
deleted
inserted
replaced
13 //#include <map> |
13 //#include <map> |
14 |
14 |
15 |
15 |
16 namespace lemon { |
16 namespace lemon { |
17 |
17 |
18 template <typename KeyType, typename KeyIntMap> |
18 template <typename Key, typename KeyIntMap> |
19 class UnionFind { |
19 class UnionFind { |
20 KeyIntMap& pointmap; |
20 KeyIntMap& pointmap; |
21 struct VectorElementType { |
21 struct VectorElementType { |
22 int boss; |
22 int boss; |
23 int count; |
23 int count; |
32 UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){ |
32 UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){ |
33 |
33 |
34 } |
34 } |
35 |
35 |
36 //Give a component of one point to the structure |
36 //Give a component of one point to the structure |
37 int addPoint(KeyType u){ |
37 int addPoint(Key u){ |
38 int _index = container.size(); |
38 int _index = container.size(); |
39 VectorElementType buf(_index,1); |
39 VectorElementType buf(_index,1); |
40 container.push_back(buf); |
40 container.push_back(buf); |
41 return _index; |
41 return _index; |
42 } |
42 } |
43 |
43 |
44 |
44 |
45 //Finds the big boss of u |
45 //Finds the big boss of u |
46 int find(KeyType u){ |
46 int find(Key u){ |
47 if (pointmap.get(u)==-1){ |
47 if (pointmap.get(u)==-1){ |
48 int whoami = addPoint(u); |
48 int whoami = addPoint(u); |
49 pointmap.set(u, whoami); |
49 pointmap.set(u, whoami); |
50 return whoami; |
50 return whoami; |
51 } |
51 } |
59 return boss; |
59 return boss; |
60 } |
60 } |
61 } |
61 } |
62 |
62 |
63 //Finds u and v in the structures and merges the comopnents, if not equal |
63 //Finds u and v in the structures and merges the comopnents, if not equal |
64 bool findAndMerge(KeyType u,KeyType v){ |
64 bool findAndMerge(Key u,Key v){ |
65 int bu = find(u); |
65 int bu = find(u); |
66 int bv = find(v); |
66 int bv = find(v); |
67 if (bu != bv){ |
67 if (bu != bv){ |
68 unio(bu,bv); |
68 unio(bu,bv); |
69 return true; |
69 return true; |