COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/unionfind.h @ 150:4b5210aa0239

Last change on this file since 150:4b5210aa0239 was 150:4b5210aa0239, checked in by beckerjc, 17 years ago

Unió-HolVan? struktúra,
Kruskal algoritmus,
hozzávaló kis tesztfájl és Makefile.

File size: 1.3 KB
Line 
1// -*- c++ -*- //
2#ifndef UNION_FIND_H
3#define UNION_FIND_H
4
5#include <vector>
6#include <utility>
7
8namespace hugo {
9
10  template <typename T, typename TIntMap>
11  class UnionFind {
12   
13  public:
14    typedef T ElementType;
15    typedef std::pair<int,int> PairType;
16
17  private:
18    std::vector<PairType> data;
19    TIntMap& map;
20
21  public:
22    UnionFind(TIntMap& m) : map(m) {}
23
24
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      }
40
41      return comp;
42    }
43
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    }
51
52    bool joinComponents(T a, T b)
53    {
54      int ca = whichComponent(a);
55      int cb = whichComponent(b);
56
57      if ( ca == cb )
58        return false;
59
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    }
70
71  };
72
73} //namespace hugo
74
75#endif //UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.