dsu_path_compression.cpp File Reference

DSU (Disjoint sets) More...

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

Include dependency graph for dsu_path_compression.cpp:

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

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

Detailed Description

DSU (Disjoint sets)

It is a very powerful data structure that 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) get_max(i),get_min(i) : returns the maximum and minimum Below is the class-based approach which uses the heuristic of path compression. Using path compression in findSet(i),we are able to get to the representative of i in O(1) time.

Author

AayushVyasKIIT

See also

dsu_union_rank.cpp

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

< number of items

< object of class disjoint sets

           {
    uint64_t n = 10;  ///< number of items
    dsu d(n + 1);     ///< object of class disjoint sets
 
    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-test implementations, 1st test.

Returns

void

< number of items

< object of class disjoint sets

                    {
    // the minimum, maximum, and size of the set
    uint64_t n = 10;  ///< number of items
    dsu d(n + 1);     ///< object of class disjoint sets
    // set 1
    d.UnionSet(1, 2);  // performs union operation on 1 and 2
    d.UnionSet(1, 4);  // performs union operation on 1 and 4
    vector<uint64_t> ans = {1, 4, 3};
    for (uint64_t i = 0; i < ans.size(); i++) {
        assert(d.get(4).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 items

< object of class disjoint sets

                    {
    // the minimum, maximum, and size of the set
    uint64_t n = 10;  ///< number of items
    dsu d(n + 1);     ///< object of class disjoint sets
    // set 1
    d.UnionSet(3, 5);
    d.UnionSet(5, 6);
    d.UnionSet(5, 7);
    vector<uint64_t> ans = {3, 7, 4};
    for (uint64_t i = 0; i < ans.size(); i++) {
        assert(d.get(3).at(i) == ans[i]);  // makes sure algorithm works fine
    }
    cout << "2nd test passed!" << endl;
}

Here is the call graph for this function: