// DisjSets class

//

// CONSTRUCTION: with int representing initial number of sets

//

// ******************PUBLIC OPERATIONS*********************

// void union( root1, root2 ) --> Merge two sets

// int find( x ) --> Return set containing x

// ******************ERRORS********************************

// No error checking is performed

#include "vector.h"

/**

* Disjoint set class.

* Does not use union heuristics or path compression.

* Elements in the set are numbered starting at 0.

*/

class DisjSets

{

public:

DisjSets( int numElements );

int find( int x ) const;

void setUnion( int root1, int root2 );

private:

vector<int> s;

};

/**

* Construct the disjoint sets object.

* numElements is the initial number of disjoint sets.

*/

DisjSets::DisjSets( int numElements ) : s( numElements )

{

for( int i = 0; i < s.size( ); i++ )

s[ i ] = -1;

}

/**

* Union two disjoint sets.

* For simplicity, we assume root1 and root2 are distinct

* and represent set names.

* root1 is the root of set 1.

* root2 is the root of set 2.

*/

void DisjSets::setUnion( int root1, int root2 )

{

s[ root2 ] = root1;

}

/**

* Perform a find.

* Error checks omitted again for simplicity.

* Return the set containing x.

*/

int DisjSets::find( int x ) const

{

if( s[ x ] < 0 )

return x;

else

return find( s[ x ] );

}

// Test main; all finds on same output line should be identical

int main( )

{

int numElements = 128;

int numInSameSet = 16;

DisjSets ds( numElements );

int set1, set2;

for( int k = 1; k < numInSameSet; k *= 2 )

{

for( int j = 0; j + k < numElements; j += 2 * k )

{

set1 = ds.find( j );

set2 = ds.find( j + k );

ds.setUnion( set1, set2 );

}

}

for( int i = 0; i < numElements; i++ )

{

cout << ds.find( i ) << "*";

if( i % numInSameSet == numInSameSet - 1 )

cout << endl;

}

cout << endl;

return 0;

}