Last change
on this file since 246:dc95ca4ebc7b was
218:5964f1c64ca1,
checked in by beckerjc, 21 years ago
|
unionfind: componentSize tagfv
kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort
nem tul elegans megoldas...
|
File size:
1.4 KB
|
Line | |
---|
1 | // -*- c++ -*- // |
---|
2 | #ifndef HUGO_UNION_FIND_H |
---|
3 | #define HUGO_UNION_FIND_H |
---|
4 | |
---|
5 | #include <vector> |
---|
6 | #include <utility> |
---|
7 | |
---|
8 | namespace 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 | int componentSize(T a) |
---|
72 | { |
---|
73 | int ca = whichComponent(a); |
---|
74 | return data[ca].second; |
---|
75 | } |
---|
76 | |
---|
77 | }; |
---|
78 | |
---|
79 | } //namespace hugo |
---|
80 | |
---|
81 | #endif //HUGO_UNION_FIND_H |
---|
Note: See
TracBrowser
for help on using the repository browser.