Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,
viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
const-os mapet is lehet set-elni...)
2 #ifndef HUGO_UNION_FIND_H
3 #define HUGO_UNION_FIND_H
10 template <typename T, typename TIntMap>
14 typedef T ElementType;
15 typedef std::pair<int,int> PairType;
18 std::vector<PairType> data;
22 UnionFind(TIntMap& m) : map(m) {}
25 int whichComponent(T a)
29 return insertNewElement(a);
33 while ( (next = data[comp].first) != comp) {
36 while ( (next = data[comp0].first) != comp) {
37 data[comp0].first = comp;
44 int insertNewElement(T a)
47 data.push_back(make_pair(n, 1));
52 bool joinComponents(T a, T b)
54 int ca = whichComponent(a);
55 int cb = whichComponent(b);
60 if ( data[ca].second > data[cb].second ) {
62 data[ca].second += data[cb].second;
66 data[cb].second += data[ca].second;
71 int componentSize(T a)
73 int ca = whichComponent(a);
74 return data[ca].second;
81 #endif //HUGO_UNION_FIND_H