Template Class DisjointSets

• Defined in File UnionFind.h

Class Documentation

template<Union L = Union::SIZE, Compression C = Compression::HALVING>
class DisjointSets

the union of disjoint sets of [ 0 , n ), the roots joined by L, the paths shortened by C

Public Functions

explicit DisjointSets(int n = 0)

the n components {0} , … , {n - 1}

Pre:

n >= 0

void reset(int n)

back to the n components {0} , … , {n - 1}

Pre:

n >= 0

inline int n(void) const

inline int count(void) const

the number of components

int find(int x)

the representative of the component of x

Pre:

x in [ 0 , n )

bool merge(int x, int y)

joins the components of x and y, the smaller (of lower rank) under the larger, under the root of y if they tie; true if they were distinct

Pre:

x , y in [ 0 , n )

bool same(int x, int y)

whether x and y are in the same component

Pre:

x , y in [ 0 , n )

int size(int x)

the number of elements of the component of x

Pre:

x in [ 0 , n ), the union by size