connected_components_with_dsu.cpp

Go to the documentation of this file.

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

namespace graph {
namespace disjoint_union {
uint32_t number_of_nodes = 0;                // denotes number of nodes
std::vector<int64_t> parent{};               // parent of each node
std::vector<uint32_t> connected_set_size{};  // size of each set
void make_set() {
    for (uint32_t i = 1; i <= number_of_nodes; i++) {
        parent[i] = i;
        connected_set_size[i] = 1;
    }
}

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

void union_sets(int64_t node1, int64_t node2) {
    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
    }
}

uint32_t no_of_connected_components() {
    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
}
}  // namespace disjoint_union
}  // namespace graph

static void test() {
    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;
}

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