unionfind.h

#ifndef UNION_FIND_H
#define UNION_FIND_H

#include <vector>
#include <stdlib.h>

class UnionFind
{
public:
  UnionFind(int entries=0);
  void Initialize(const int entries);
  void Resize(const int entries);
  int AddEntry();
  int FindSet(const int i);  
  int Union(const int i,const int j);
  void GetSets(std::vector<int>& sets);
  size_t CountSets() const;
  void GetRoots(std::vector<int>& roots) const;
  void EnumerateSets(std::vector<std::vector<int> >& sets) const;
  void EnumerateSet(int i,std::vector<int>& s) const;

  //low level routines
  inline bool IsRoot(const int i) const { return parents[i]==-1; }
  int FindRoot(const int i) const;

private:
  std::vector<int> parents;
  void PathCompress(const int i,const int root);
  void CompressAll();
};
#endif