GitHunt
AR

Aryan-Jha29/DSU_Cpp17_HeaderFile

Implementation of Disjoint Set Union Header File(.hpp) from scratch using object-oriented design approach.

Disjoint-Set-Union-Header

forthebadge forthebadge forthebadge

Implementation of Disjoint Set Union Header File(.hpp) from scratch using object oriented design approach.

How to use?

  • disjoint_set.hpp file must be present in the present working directory or its path must be set in the environment variable for the IDE.
  • Compatible C++ versions: C++11, C++14, C++17, C++20

Key Functionalities

  • To create a DSU(Disjoint Set Union) with N groups.
  • To merge two set with given node_ids.
    • Implemented Union-By-Rank to perform optimsed merger of nodes.
  • To find the parent_node for a given input node.
    • Implemented Path Compression to optimise the method.
  • To perform validation of nodes with the given node_id.
  • To detect existence of a cycle by utilising the find_parent method.
  • To obtain the total count of disjoint sets in O(1)
  • To obtain the size of the set to which a given node belongs in O(1)

Sample C++ template:

    #include <bits/stdc++.h>
    #include "disjoint_set.hpp"

    using namespace std;
    int main()
    {
        int N;
        cin>>N;
        disjoint_set<int> ds(N);
        // code goes here
    }      

Methods

disjoint_set:: method()

  • bool is_valid(datatype &)
  • datatype find_parent(datatype)
  • void union_set(datatype, datatype)
  • bool detect_cycle(datatype &, datatype &)
  • datatype get_dsu_count()
  • datatype get_set_count(datatype)

MIT LICENSE

Authors

Languages

C++88.8%Makefile11.2%

Contributors

MIT License
Created October 26, 2021
Updated January 29, 2023