dsu_union_rank.cpp File Reference

DSU (Disjoint sets) More...

#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for dsu_union_rank.cpp:

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

Functions
static void	test1 ()
	Self-implementations, 1st test. More...
static void	test2 ()
	Self-implementations, 2nd test. More...
int	main ()
	Main function. More...

Detailed Description

DSU (Disjoint sets)

dsu : It is a very powerful data structure which keeps track of different clusters(sets) of elements, these sets are disjoint(doesnot have a common element). Disjoint sets uses cases : for finding connected components in a graph, used in Kruskal's algorithm for finding Minimum Spanning tree. Operations that can be performed: 1) UnionSet(i,j): add(element i and j to the set) 2) findSet(i): returns the representative of the set to which i belogngs to. 3) getParents(i): prints the parent of i and so on and so forth. Below is the class-based approach which uses the heuristic of union-ranks. Using union-rank in findSet(i),we are able to get to the representative of i in slightly delayed O(logN) time but it allows us to keep tracks of the parent of i.

Author

AayushVyasKIIT

See also

dsu_path_compression.cpp

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test1();  // run 1st test case
    test2();  // run 2nd test case
 
    return 0;
}

Here is the call graph for this function:

test1()

static void test1 ( )

static

Self-implementations, 1st test.

Returns

void

< number of elements

< object of class disjoint sets

< performs union operation on 1 and 2

                    {
    /* checks the parents in the resultant structures */
    uint64_t n = 10;   ///< number of elements
    dsu d(n + 1);      ///< object of class disjoint sets
    d.unionSet(2, 1);  ///< performs union operation on 1 and 2
    d.unionSet(1, 4);
    d.unionSet(8, 1);
    d.unionSet(3, 5);
    d.unionSet(5, 6);
    d.unionSet(5, 7);
    d.unionSet(9, 10);
    d.unionSet(2, 10);
    // keeping track of the changes using parent pointers
    vector<uint64_t> ans = {7, 5};
    for (uint64_t i = 0; i < ans.size(); i++) {
        assert(d.getParents(7).at(i) ==
               ans[i]);  // makes sure algorithm works fine
    }
    cout << "1st test passed!" << endl;
}

Here is the call graph for this function:

test2()

static void test2 ( )

static

Self-implementations, 2nd test.

Returns

void

< number of elements

< object of class disjoint sets

performs union operation on 1 and 2

keeping track of the changes using parent pointers

makes sure algorithm works fine

                    {
    // checks the parents in the resultant structures
    uint64_t n = 10;   ///< number of elements
    dsu d(n + 1);      ///< object of class disjoint sets
    d.unionSet(2, 1);  /// performs union operation on 1 and 2
    d.unionSet(1, 4);
    d.unionSet(8, 1);
    d.unionSet(3, 5);
    d.unionSet(5, 6);
    d.unionSet(5, 7);
    d.unionSet(9, 10);
    d.unionSet(2, 10);
 
    /// keeping track of the changes using parent pointers
    vector<uint64_t> ans = {2, 1, 10};
    for (uint64_t i = 0; i < ans.size(); i++) {
        assert(d.getParents(2).at(i) ==
               ans[i]);  /// makes sure algorithm works fine
    }
    cout << "2nd test passed!" << endl;
}

Here is the call graph for this function: