Advertisement
jasonpogi1669

Disjoint set UNION by RANK and Path Compression using C++

Sep 1st, 2021
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node {
  6.     int parent;
  7.     int rank;
  8. };
  9.  
  10. vector<node> dsuf;
  11.  
  12. int Find(int v) {
  13.     // traverse the tree structure and apply path compression
  14.     if (dsuf[v].parent == -1) {
  15.         return v;
  16.     }
  17.     return dsuf[v].parent = Find(dsuf[v].parent);
  18. }
  19.  
  20. void Union(int root_of_from, int root_of_to) {
  21.     // there will be three cases in merging the subsets:
  22.     // case 1 - if the rank of the absolute root (parent) of 'from' is greater than the absolute root (parent)
  23.     // of 'to', then set the absolute root (parent) of 'to' to the absolute root (parent) of 'from'
  24.     // case 2 - if the rank of the absolute root (parent) of 'from' is less than the absolute root (parent)
  25.     // of 'to', then set the absolute root (parent) of 'from' tot the absolute root (parent) of 'to'
  26.     // cae 3 - if the ranks of the absolute roots of the two vertices given ('from' and 'to') are the
  27.     // same, then arbitrarily choose one among them to be the absolute root (parent ) of the other vertex
  28.     // and do not forget to increase the rank of the newly chosen absolute root (parent)
  29.     if (dsuf[root_of_from].rank > dsuf[root_of_to].rank) {
  30.         dsuf[root_of_to].parent = root_of_from;
  31.     } else if (dsuf[root_of_from].rank < dsuf[root_of_to].rank) {
  32.         dsuf[root_of_from].parent = root_of_to;
  33.     } else {
  34.         dsuf[root_of_from].parent = root_of_to;
  35.         dsuf[root_of_to].rank++;
  36.     }
  37. }
  38.  
  39. bool IsCyclic(vector<pair<int, int>>& edge_list) {
  40.     for (auto& p : edge_list) {
  41.         // find the absolute roots (parents) of the two vertices and check if it forms a cycle,
  42.         // then merge the vertices in one subset by making their absolute root the same
  43.         int root_of_from = Find(p.first);
  44.         int root_of_to = Find(p.second);
  45.         if (root_of_from == root_of_to) {
  46.             return true;
  47.         }
  48.         Union(root_of_from, root_of_to);
  49.     }
  50.     return false;
  51. }
  52.  
  53. int main() {
  54.     // input number of edges and vertices
  55.     int E, V;
  56.     cin >> E >> V;
  57.     // mark all vertices as separate subsets with only one (1) element
  58.     // create an adjacency list (using nodes) and set their parent and rank to -1 and 0 respectively
  59.     dsuf.resize(V);
  60.     for (int i = 0; i < V; i++){
  61.         dsuf[i].parent = -1;
  62.         dsuf[i].rank = 0;
  63.     }
  64.     // form the edges of every two vertices
  65.     vector<pair<int, int>> edge_list;
  66.     for (int i = 0; i < E; i++) {
  67.         int from, to;
  68.         cin >> from >> to;
  69.         edge_list.push_back(make_pair(from, to));
  70.     }
  71.     // check if the tree structure forms a cycle
  72.     if (IsCyclic(edge_list)) {
  73.         cout << "TRUE";
  74.     } else {
  75.         cout << "FALSE";
  76.     }
  77.     cout << '\n';
  78.     return 0;
  79. }
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement