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