Thea

Unionfind data structure. More...
#include <UnionFind.hpp>
Public Member Functions  
intx  find (intx p) const 
Return the ID of the representative element of the set corresponding to the object with ID p. More...  
intx  getObjectId (T const &obj) const 
Get the ID of an object, or a negative value if it is not present in the data structure. More...  
void  merge (intx x, intx y) 
Replace sets containing x and y with their union. More...  
intx  numSets () const 
Get the number of disjoint sets. More...  
bool  sameSet (intx x, intx y) const 
Are objects x and y in the same set? More...  
intx  sizeOfSet (intx p) const 
Get the size of the set containing object p. More...  
UnionFind (intx n)  
Create a unionfind data structure for n objects, which will be assumed to have sequential IDs from 0 to n  1. More...  
template<typename InputIterator >  
UnionFind (InputIterator begin, InputIterator end)  
Create a unionfind data structure for objects in the range [begin, end). More...  
~UnionFind ()  
Destructor. More...  
Unionfind data structure.
Original code by Kartik Kukreja, https://github.com/kartikkukreja/ . The data structure will save a copy of each object to support getObjectId(), so T should be easily copyable (a small/POD class, or a pointer).
Definition at line 28 of file UnionFind.hpp.
Create a unionfind data structure for n objects, which will be assumed to have sequential IDs from 0 to n  1.
If you use this constructor, note that getObjectId() will return the expected results (operating as an identity function) only if T = intx
. Else, avoid calling getObjectId().
Definition at line 36 of file UnionFind.hpp.
UnionFind  (  InputIterator  begin, 
InputIterator  end  
) 
Create a unionfind data structure for objects in the range [begin, end).
The objects will be assigned sequential IDs 0, 1, 2, ..., n  1 in the same order as the input. Note that the data structure will save a copy of each object to support getObjectId(), so T should be easily copyable (a small/POD class, or a pointer).
Definition at line 47 of file UnionFind.hpp.
~UnionFind  (  ) 
Destructor.
Definition at line 58 of file UnionFind.hpp.
Return the ID of the representative element of the set corresponding to the object with ID p.
Definition at line 76 of file UnionFind.hpp.
intx getObjectId  (  T const &  obj  )  const 
Get the ID of an object, or a negative value if it is not present in the data structure.
Note that if you used the UnionFind(intx) constructor, this function will give the expected results (operating as an identity function) only if T = intx
.
Definition at line 69 of file UnionFind.hpp.
Replace sets containing x and y with their union.
Definition at line 94 of file UnionFind.hpp.
intx numSets  (  )  const 
Get the number of disjoint sets.
Definition at line 124 of file UnionFind.hpp.
Are objects x and y in the same set?
Definition at line 118 of file UnionFind.hpp.
Get the size of the set containing object p.
Definition at line 130 of file UnionFind.hpp.