Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
connected_components_with_dsu.cpp File Reference

Disjoint union More...

#include <iostream>
#include <set>
#include <vector>
Include dependency graph for connected_components_with_dsu.cpp:

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

Function Documentation

◆ find_set()

int64_t graph::disjoint_union::find_set ( int64_t val)

Find the component where following node belongs to.

Parameters
valparent of val should be found
Returns
parent of val
49 {
50 while (parent[val] != val) {
51 parent[val] = parent[parent[val]];
52 val = parent[val];
53 }
54 return val;
55}
Here is the call graph for this function:

◆ main()

int main ( void )

Main function.

Returns
0 on exit
112 {
113 test(); // Execute the tests
114 return 0;
115}
static void test()
Test Implementations.
Definition connected_components_with_dsu.cpp:92
Here is the call graph for this function:

◆ make_set()

void graph::disjoint_union::make_set ( )

function the initialize every node as it's own parent

Returns
void
38 {
39 for (uint32_t i = 1; i <= number_of_nodes; i++) {
40 parent[i] = i;
41 connected_set_size[i] = 1;
42 }
43}
Here is the call graph for this function:

◆ no_of_connected_components()

uint32_t graph::disjoint_union::no_of_connected_components ( )

Find total no. of connected components.

Returns
Number of connected components
80 {
81 std::set<int64_t> temp; // temp set to count number of connected components
82 for (uint32_t i = 1; i <= number_of_nodes; i++) temp.insert(find_set(i));
83 return temp.size(); // return the size of temp set
84}
int64_t find_set(int64_t val)
Find the component where following node belongs to.
Definition connected_components_with_dsu.cpp:49
T insert(T... args)
T size(T... args)
Here is the call graph for this function:

◆ test()

static void test ( )
static

Test Implementations.

Returns
void
92 {
93 namespace dsu = graph::disjoint_union;
94 std::cin >> dsu::number_of_nodes;
95 dsu::parent.resize(dsu::number_of_nodes + 1);
96 dsu::connected_set_size.resize(dsu::number_of_nodes + 1);
97 dsu::make_set();
98 uint32_t edges = 0;
99 std::cin >> edges; // no of edges in the graph
100 while (edges--) {
101 int64_t node_a = 0, node_b = 0;
102 std::cin >> node_a >> node_b;
103 dsu::union_sets(node_a, node_b);
104 }
105 std::cout << dsu::no_of_connected_components() << std::endl;
106}
Disjoint sets union data structure, class based representation.
Definition dsu_path_compression.cpp:33
T endl(T... args)
Here is the call graph for this function:

◆ union_sets()

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

Merge 2 components to become one.

Parameters
node11st component
node22nd component
Returns
void
62 {
63 node1 = find_set(node1); // find the parent of node1
64 node2 = find_set(node2); // find the parent of node2
65
66 // If parents of both nodes are not same, combine them
67 if (node1 != node2) {
68 if (connected_set_size[node1] < connected_set_size[node2]) {
69 std::swap(node1, node2); // swap both components
70 }
71 parent[node2] = node1; // make node1 as parent of node2.
72 connected_set_size[node1] +=
73 connected_set_size[node2]; // sum the size of both as they combined
74 }
75}
T swap(T... args)
Here is the call graph for this function:

Variable Documentation

◆ connected_set_size

std::vector<uint32_t> graph::disjoint_union::connected_set_size {}
33{}; // size of each set

◆ parent

std::vector<int64_t> graph::disjoint_union::parent {}
32{}; // parent of each node