connected_components_with_dsu.cpp File Reference

Disjoint union More...

#include <cstdint>
#include <iostream>
#include <set>
#include <vector>

Include dependency graph for connected_components_with_dsu.cpp:

Go to the source code of this file.

Namespaces
namespace	graph
	Graph Algorithms.
namespace	disjoint_union
	Functions for Disjoint union implementation.

Functions
void	graph::disjoint_union::make_set ()
	function the initialize every node as it's own parent
int64_t	graph::disjoint_union::find_set (int64_t val)
	Find the component where following node belongs to.
void	graph::disjoint_union::union_sets (int64_t node1, int64_t node2)
	Merge 2 components to become one.
uint32_t	graph::disjoint_union::no_of_connected_components ()
	Find total no. of connected components.
static void	test ()
	Test Implementations.
int	main ()
	Main function.

Variables
uint32_t	graph::disjoint_union::number_of_nodes = 0
std::vector< int64_t >	graph::disjoint_union::parent {}
std::vector< uint32_t >	graph::disjoint_union::connected_set_size {}

Detailed Description

Disjoint union

The Disjoint union is the technique to find connected component in graph efficiently.

Algorithm

In Graph, if you have to find out the number of connected components, there are 2 options

1. Depth first search
2. Disjoint union 1st option is inefficient, Disjoint union is the most optimal way to find this.

Author

Unknown author

Sagar Pandya

Definition in file connected_components_with_dsu.cpp.

Function Documentation

find_set()

int64_t graph::disjoint_union::find_set

(

int64_t

val

)

Find the component where following node belongs to.

Parameters

val	parent of val should be found

Returns

parent of val

Definition at line 54 of file connected_components_with_dsu.cpp.

                              {
    while (parent[val] != val) {
        parent[val] = parent[parent[val]];
        val = parent[val];
    }
    return val;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 117 of file connected_components_with_dsu.cpp.

           {
    test();  // Execute the tests
    return 0;
}

make_set()

void graph::disjoint_union::make_set

(

)

function the initialize every node as it's own parent

Returns

void

Definition at line 43 of file connected_components_with_dsu.cpp.

                {
    for (uint32_t i = 1; i <= number_of_nodes; i++) {
        parent[i] = i;
        connected_set_size[i] = 1;
    }
}

no_of_connected_components()

uint32_t graph::disjoint_union::no_of_connected_components

(

)

Find total no. of connected components.

Returns

Number of connected components

Definition at line 85 of file connected_components_with_dsu.cpp.

                                      {
    std::set<int64_t> temp;  // temp set to count number of connected components
    for (uint32_t i = 1; i <= number_of_nodes; i++) temp.insert(find_set(i));
    return temp.size();  // return the size of temp set
}

test()

static void test ( )

static

Test Implementations.

Returns

void

Definition at line 97 of file connected_components_with_dsu.cpp.

                   {
    namespace dsu = graph::disjoint_union;
    std::cin >> dsu::number_of_nodes;
    dsu::parent.resize(dsu::number_of_nodes + 1);
    dsu::connected_set_size.resize(dsu::number_of_nodes + 1);
    dsu::make_set();
    uint32_t edges = 0;
    std::cin >> edges;  // no of edges in the graph
    while (edges--) {
        int64_t node_a = 0, node_b = 0;
        std::cin >> node_a >> node_b;
        dsu::union_sets(node_a, node_b);
    }
    std::cout << dsu::no_of_connected_components() << std::endl;
}

union_sets()

void graph::disjoint_union::union_sets	(	int64_t	node1,
		int64_t	node2 )

Merge 2 components to become one.

Parameters

node1	1st component
node2	2nd component

Returns

void

Definition at line 67 of file connected_components_with_dsu.cpp.

                                              {
    node1 = find_set(node1);  // find the parent of node1
    node2 = find_set(node2);  // find the parent of node2
 
    // If parents of both nodes are not same, combine them
    if (node1 != node2) {
        if (connected_set_size[node1] < connected_set_size[node2]) {
            std::swap(node1, node2);  // swap both components
        }
        parent[node2] = node1;  // make node1 as parent of node2.
        connected_set_size[node1] +=
            connected_set_size[node2];  // sum the size of both as they combined
    }
}

Variable Documentation

connected_set_size

std::vector<uint32_t> graph::disjoint_union::connected_set_size {}

Definition at line 38 of file connected_components_with_dsu.cpp.

{};  // size of each set

number_of_nodes

uint32_t graph::disjoint_union::number_of_nodes = 0

Definition at line 36 of file connected_components_with_dsu.cpp.

parent

std::vector<int64_t> graph::disjoint_union::parent {}

Definition at line 37 of file connected_components_with_dsu.cpp.

{};               // parent of each node