00001
00007 #ifndef DISJOINT_SET_HPP
00008 #define DISJOINT_SET_HPP
00009
00010 #include <vector>
00011
00020 class DisjointSet
00021 {
00022 public:
00029 DisjointSet( unsigned int numItems );
00037 DisjointSet( const DisjointSet & that );
00042 ~DisjointSet();
00043
00055 void setUnion( unsigned int x, unsigned int y );
00063 unsigned int find( unsigned int x ) const;
00074 void split( unsigned int x, unsigned int y );
00075
00087 void getSetSizes( std::vector<unsigned int> & sizes ) const;
00093 void print() const;
00094
00101 DisjointSet & operator=( const DisjointSet & that );
00102
00103 private:
00104 unsigned int mNumItems;
00105 unsigned int *mParents;
00106 unsigned int *mSizes;
00107
00116 bool isRepresentative( unsigned int x ) const
00117 {
00118 return mParents[x] == x;
00119 };
00120
00128 void rebase( unsigned int x );
00129 };
00130
00131 #endif
00132