#ifndef DISJSET_H_INC
#define DISJSET_H_INC

// DisjSets class
//
// CONSTRUCTION: with long representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union( root1, root2 ) --> Merge two sets
// long find( x )             --> Return set containing x
// ******************ERRORS********************************
// BadArgument exception thrown as needed.

#include <vector>

// Disjoint set class.
// Use union by rank and path compression.
// Elements in the set are numbered starting at 0.
class DisjSet
{
public:
    DisjSet( long numElements );

    long find( long x ) const;
    long find( long x );
    void unionSets( long root1, long root2 );

private:
    std::vector<long> s;
    void assertIsRoot( long root ) const;
    void assertIsItem( long item ) const;
};

#endif