Skip to content

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

License

Notifications You must be signed in to change notification settings

Aryan-Jha29/DSU_Cpp17_HeaderFile

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

22 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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)

CopyRight & License

MIT LICENSE

Authors

About

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

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published