dsu Class Reference

Disjoint sets union data structure, class based representation. More...

Collaboration diagram for dsu:

Public Member Functions
	dsu (uint64_t n)
	contructor for initialising all data members.
uint64_t	findSet (uint64_t i)
	Method to find the representative of the set to which i belongs to, T(n) = O(1)
void	UnionSet (uint64_t i, uint64_t j)
	Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.
bool	isSame (uint64_t i, uint64_t j)
	A utility function which check whether i and j belongs to same set or not.
vector< uint64_t >	get (uint64_t i)
	prints the minimum, maximum and size of the set to which i belongs to
uint64_t	size (uint64_t i)
	A utility function that returns the size of the set to which i belongs to.
uint64_t	get_max (uint64_t i)
	A utility function that returns the max element of the set to which i belongs to.
uint64_t	get_min (uint64_t i)
	A utility function that returns the min element of the set to which i belongs to.
	dsu (uint64_t n)
	constructor for initialising all data members
uint64_t	findSet (uint64_t i)
	Method to find the representative of the set to which i belongs to, T(n) = O(logN)
void	unionSet (uint64_t i, uint64_t j)
	Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.
bool	isSame (uint64_t i, uint64_t j)
	A utility function which check whether i and j belongs to same set or not.
vector< uint64_t >	getParents (uint64_t i)
	Method to print all the parents of i, or the path from i to representative.

Private Attributes
vector< uint64_t >	p
	keeps track of the parent of ith element
vector< uint64_t >	depth
	tracks the depth(rank) of i in the tree
vector< uint64_t >	setSize
	size of each chunk(set)
vector< uint64_t >	maxElement
	maximum of each set to which i belongs to
vector< uint64_t >	minElement
	minimum of each set to which i belongs to

Detailed Description

Disjoint sets union data structure, class based representation.

Parameters

n	number of elements

Constructor & Destructor Documentation

dsu() [1/2]

dsu::dsu ( uint64_t n )

inlineexplicit

contructor for initialising all data members.

Parameters

n	number of elements

initially, all of them are their own parents

initially all have depth are equals to zero

initially set size will be equals to one

                             {
        p.assign(n, 0);
        /// initially, all of them are their own parents
        for (uint64_t i = 0; i < n; i++) {
            p[i] = i;
        }
        /// initially all have depth are equals to zero
        depth.assign(n, 0);
        maxElement.assign(n, 0);
        minElement.assign(n, 0);
        for (uint64_t i = 0; i < n; i++) {
            depth[i] = 0;
            maxElement[i] = i;
            minElement[i] = i;
        }
        setSize.assign(n, 0);
        /// initially set size will be equals to one
        for (uint64_t i = 0; i < n; i++) {
            setSize[i] = 1;
        }
    }

Here is the call graph for this function:

dsu() [2/2]

dsu::dsu ( uint64_t n )

inlineexplicit

constructor for initialising all data members

Parameters

n	number of elements

initially all of them are their own parents

                             {
        p.assign(n, 0);
        /// initially all of them are their own parents
        depth.assign(n, 0);
        setSize.assign(n, 0);
        for (uint64_t i = 0; i < n; i++) {
            p[i] = i;
            depth[i] = 0;
            setSize[i] = 1;
        }
    }

Here is the call graph for this function:

Member Function Documentation

findSet() [1/2]

uint64_t dsu::findSet ( uint64_t i )

inline

Method to find the representative of the set to which i belongs to, T(n) = O(1)

Parameters

i	element of some set

Returns

representative of the set to which i belongs to.

using path compression

                                 {
        /// using path compression
        if (p[i] == i) {
            return i;
        }
        return (p[i] = findSet(p[i]));
    }

Here is the call graph for this function:

findSet() [2/2]

uint64_t dsu::findSet ( uint64_t i )

inline

Method to find the representative of the set to which i belongs to, T(n) = O(logN)

Parameters

i	element of some set

Returns

representative of the set to which i belongs to

using union-rank

                                 {
        /// using union-rank
        while (i != p[i]) {
            i = p[i];
        }
        return i;
    }

get()

vector< uint64_t > dsu::get ( uint64_t i )

inline

prints the minimum, maximum and size of the set to which i belongs to

Parameters

i	element of some set

Returns

void

                                     {
        vector<uint64_t> ans;
        ans.push_back(get_min(i));
        ans.push_back(get_max(i));
        ans.push_back(size(i));
        return ans;
    }

Here is the call graph for this function:

get_max()

uint64_t dsu::get_max ( uint64_t i )

inline

A utility function that returns the max element of the set to which i belongs to.

Parameters

i	element of some set

Returns

maximum of the set to which i belongs to

{ return maxElement[findSet(i)]; }

Here is the call graph for this function:

get_min()

uint64_t dsu::get_min ( uint64_t i )

inline

A utility function that returns the min element of the set to which i belongs to.

Parameters

i	element of some set

Returns

minimum of the set to which i belongs to

{ return minElement[findSet(i)]; }

Here is the call graph for this function:

getParents()

vector< uint64_t > dsu::getParents ( uint64_t i )

inline

Method to print all the parents of i, or the path from i to representative.

Parameters

i	element of some set

Returns

void

                                            {
        vector<uint64_t> ans;
        while (p[i] != i) {
            ans.push_back(i);
            i = p[i];
        }
        ans.push_back(i);
        return ans;
    }

isSame() [1/2]

bool dsu::isSame ( uint64_t i, uint64_t j )

inline

A utility function which check whether i and j belongs to same set or not.

Parameters

i	element of some set
j	element of some set

Returns

true if element i and j ARE in the same set

false if element i and j are NOT in same set

                                        {
        if (findSet(i) == findSet(j)) {
            return true;
        }
        return false;
    }

Here is the call graph for this function:

isSame() [2/2]

bool dsu::isSame ( uint64_t i, uint64_t j )

inline

A utility function which check whether i and j belongs to same set or not.

Parameters

i	element of some set
j	element of some set

Returns

true if element i and j are in same set

false if element i and j are not in same set

                                        {
        if (findSet(i) == findSet(j)) {
            return true;
        }
        return false;
    }

Here is the call graph for this function:

size()

uint64_t dsu::size ( uint64_t i )

inline

A utility function that returns the size of the set to which i belongs to.

Parameters

i	element of some set

Returns

size of the set to which i belongs to

{ return setSize[findSet(i)]; }

Here is the call graph for this function:

UnionSet()

void dsu::UnionSet ( uint64_t i, uint64_t j )

inline

Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.

Parameters

i	element of some set
j	element of some set

Returns

void

check if both belongs to the same set or not

always keeping the min as x shallow tree

making the shallower root's parent the deeper root

if same depth, then increase one's depth

total size of the resultant set

changing the maximum elements

                                          {
        /// check if both belongs to the same set or not
        if (isSame(i, j)) {
            return;
        }
 
        // we find the representative of the i and j
        uint64_t x = findSet(i);
        uint64_t y = findSet(j);
 
        /// always keeping the min as x
        /// shallow tree
        if (depth[x] > depth[y]) {
            std::swap(x, y);
        }
        /// making the shallower root's parent the deeper root
        p[x] = y;
 
        /// if same depth, then increase one's depth
        if (depth[x] == depth[y]) {
            depth[y]++;
        }
        /// total size of the resultant set
        setSize[y] += setSize[x];
        /// changing the maximum elements
        maxElement[y] = std::max(maxElement[x], maxElement[y]);
        minElement[y] = std::min(minElement[x], minElement[y]);
    }

Here is the call graph for this function:

unionSet()

void dsu::unionSet ( uint64_t i, uint64_t j )

inline

Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.

Parameters

i	element of some set
j	element of some set

Returns

void

checks if both belongs to same set or not

we find representative of the i and j

always keeping the min as x in order to create a shallow tree

making the shallower tree, root parent of the deeper root

if same depth, then increase one's depth

total size of the resultant set

                                          {
        /// checks if both belongs to same set or not
        if (isSame(i, j)) {
            return;
        }
        /// we find representative of the i and j
        uint64_t x = findSet(i);
        uint64_t y = findSet(j);
 
        /// always keeping the min as x
        /// in order to create a shallow tree
        if (depth[x] > depth[y]) {
            std::swap(x, y);
        }
        /// making the shallower tree, root parent of the deeper root
        p[x] = y;
 
        /// if same depth, then increase one's depth
        if (depth[x] == depth[y]) {
            depth[y]++;
        }
        /// total size of the resultant set
        setSize[y] += setSize[x];
    }

Here is the call graph for this function:

---

The documentation for this class was generated from the following files:

• data_structures/dsu_path_compression.cpp
• data_structures/dsu_union_rank.cpp