dsu Class Reference

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

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

Definition at line 34 of file dsu_path_compression.cpp.

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

Definition at line 46 of file dsu_path_compression.cpp.

                             {
        p.assign(n, 0);
        for (uint64_t i = 0; i < n; i++) {
            p[i] = i;
        }
        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);
        for (uint64_t i = 0; i < n; i++) {
            setSize[i] = 1;
        }
    }

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

Definition at line 45 of file dsu_union_rank.cpp.

                             {
        p.assign(n, 0);
        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;
        }
    }

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

Definition at line 74 of file dsu_path_compression.cpp.

                                 {
        if (p[i] == i) {
            return i;
        }
        return (p[i] = findSet(p[i]));
    }

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

Definition at line 62 of file dsu_union_rank.cpp.

                                 {
        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

Definition at line 136 of file dsu_path_compression.cpp.

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

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

Definition at line 156 of file dsu_path_compression.cpp.

{ return maxElement[findSet(i)]; }

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

Definition at line 163 of file dsu_path_compression.cpp.

{ return minElement[findSet(i)]; }

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

Definition at line 120 of file dsu_union_rank.cpp.

                                            {
        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

Definition at line 124 of file dsu_path_compression.cpp.

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

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

Definition at line 108 of file dsu_union_rank.cpp.

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

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

Definition at line 149 of file dsu_path_compression.cpp.

{ return setSize[findSet(i)]; }

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

Definition at line 88 of file dsu_path_compression.cpp.

                                          {
        if (isSame(i, j)) {
            return;
        }
 
        // we find the representative of the i and j
        uint64_t x = findSet(i);
        uint64_t y = findSet(j);
 
        if (depth[x] > depth[y]) {
            std::swap(x, y);
        }
        p[x] = y;
 
        if (depth[x] == depth[y]) {
            depth[y]++;
        }
        setSize[y] += setSize[x];
        maxElement[y] = std::max(maxElement[x], maxElement[y]);
        minElement[y] = std::min(minElement[x], minElement[y]);
    }

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

Definition at line 76 of file dsu_union_rank.cpp.

                                          {
        if (isSame(i, j)) {
            return;
        }
        uint64_t x = findSet(i);
        uint64_t y = findSet(j);
 
        if (depth[x] > depth[y]) {
            std::swap(x, y);
        }
        p[x] = y;
 
        if (depth[x] == depth[y]) {
            depth[y]++;
        }
        setSize[y] += setSize[x];
    }

Member Data Documentation

depth

vector< uint64_t > dsu::depth

private

tracks the depth(rank) of i in the tree

Definition at line 37 of file dsu_path_compression.cpp.

maxElement

vector<uint64_t> dsu::maxElement

private

maximum of each set to which i belongs to

Definition at line 39 of file dsu_path_compression.cpp.

minElement

vector<uint64_t> dsu::minElement

private

minimum of each set to which i belongs to

Definition at line 40 of file dsu_path_compression.cpp.

p

vector< uint64_t > dsu::p

private

keeps track of the parent of ith element

Definition at line 36 of file dsu_path_compression.cpp.

setSize

vector< uint64_t > dsu::setSize

private

size of each chunk(set)

Definition at line 38 of file dsu_path_compression.cpp.

---

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

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