Class MFSet

• Defined in File MFSet.h

Class Documentation

class MFSet

the union of disjoint sets on a forest

Public Types

enum class Union

how merge() chooses the root that goes under the other one

Values:

enumerator NONE

the root of y under that of x

enumerator RANK

the lower tree under the higher one

enumerator SIZE

the smaller tree under the larger one

Public Functions

explicit MFSet(int n, Union u = Union::RANK, bool compress = true)

Mfset( n ): the n components {0} , … , {n - 1}, with the given union and with the compression of the paths or not.

Pre:

n >= 0

int n(void) const

int count(void) const

the number of components

int find(int x)

the representative of the component of x, the root of its tree

Pre:

x in [ 0 , n )

Post:

the result is a root

bool merge(int x, int y)

joins the components of x and y; true if they were distinct

Pre:

x , y in [ 0 , n )

Post:

x and y are in the same component

bool same(int x, int y)

true if x and y are in the same component, find( x ) == find( y )

Pre:

x , y in [ 0 , n )

int parent(int x) const

the parent of x, x itself if a root

Pre:

x in [ 0 , n )

int rank(int x) const

the rank of x

Pre:

x in [ 0 , n )

int size(int x) const

the number of nodes of the tree of x, if x is a root and the union is by size

Pre:

x in [ 0 , n )

long steps(void) const

the steps up the trees made by find() so far