Connected Components with Dsu

/**
 * @file
 * @brief [Disjoint union](https://en.wikipedia.org/wiki/Disjoint_union)
 *
 * @details
 * 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
 * @author [Sagar Pandya](https://github.com/sagarpandyansit)
 */
#include <iostream> /// for IO operations
#include <set>    /// for std::set
#include <vector> /// for std::vector

/**
 * @namespace graph
 * @brief Graph Algorithms
 */
namespace graph {
/**
 * @namespace disjoint_union
 * @brief Functions for [Disjoint union](https://en.wikipedia.org/wiki/Disjoint_union) implementation
 */
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
/**
 * @brief function the initialize every node as it's own parent
 * @returns void
 */
void make_set() {
    for (uint32_t i = 1; i <= number_of_nodes; i++) {
        parent[i] = i;
        connected_set_size[i] = 1;
    }
}
/**
 * @brief Find the component where following node belongs to
 * @param val parent of val should be found
 * @return parent of val
 */
int64_t find_set(int64_t val) {
    while (parent[val] != val) {
        parent[val] = parent[parent[val]];
        val = parent[val];
    }
    return val;
}
/**
 * @brief Merge 2 components to become one
 * @param node1 1st component
 * @param node2 2nd component
 * @returns void
 */
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
    }
}
/**
 * @brief Find total no. of connected components
 * @return Number of connected components
 */
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

/**
 * @brief Test Implementations
 * @returns void
 */
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;
}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    test();  // Execute the tests
    return 0;
}
Algerlogo

Β© Alger 2022

About us

We are a group of programmers helping each other build new things, whether it be writing complex encryption programs, or simple ciphers. Our goal is to work together to document and model beautiful, helpful and interesting algorithms using code. We are an open-source community - anyone can contribute. We check each other's work, communicate and collaborate to solve problems. We strive to be welcoming, respectful, yet make sure that our code follows the latest programming guidelines.