| author | marci |
| Wed, 17 Mar 2004 16:10:33 +0000 | |
| changeset 196 | 8a9b9360463e |
| child 218 | 5964f1c64ca1 |
| permissions | -rw-r--r-- |
1 // -*- c++ -*- //
2 #ifndef UNION_FIND_H
3 #define UNION_FIND_H
5 #include <vector>
6 #include <utility>
8 namespace hugo {
10 template <typename T, typename TIntMap>
11 class UnionFind {
13 public:
14 typedef T ElementType;
15 typedef std::pair<int,int> PairType;
17 private:
18 std::vector<PairType> data;
19 TIntMap& map;
21 public:
22 UnionFind(TIntMap& m) : map(m) {}
25 int whichComponent(T a)
26 {
27 int comp0 = map.get(a);
28 if (comp0 < 0) {
29 return insertNewElement(a);
30 }
31 int comp = comp0;
32 int next;
33 while ( (next = data[comp].first) != comp) {
34 comp = next;
35 }
36 while ( (next = data[comp0].first) != comp) {
37 data[comp0].first = comp;
38 comp0 = next;
39 }
41 return comp;
42 }
44 int insertNewElement(T a)
45 {
46 int n = data.size();
47 data.push_back(make_pair(n, 1));
48 map.set(a,n);
49 return n;
50 }
52 bool joinComponents(T a, T b)
53 {
54 int ca = whichComponent(a);
55 int cb = whichComponent(b);
57 if ( ca == cb )
58 return false;
60 if ( data[ca].second > data[cb].second ) {
61 data[cb].first = ca;
62 data[ca].second += data[cb].second;
63 }
64 else {
65 data[ca].first = cb;
66 data[cb].second += data[ca].second;
67 }
68 return true;
69 }
71 };
73 } //namespace hugo
75 #endif //UNION_FIND_H