SHARE
TWEET

DisjointSet

adnan_dipta89 Oct 21st, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class disjointSet
  5. {
  6.     public:
  7.     int *_rank, *parent,n;
  8.     disjointSet(int n)
  9.     {
  10.         _rank = new int[n+1];
  11.         parent =  new int[n+1];
  12.         this->n = n;
  13.         MakeSet();
  14.     }
  15.     void MakeSet()
  16.     {
  17.         for(int i = 1; i <= n; i++)
  18.         {
  19.             parent[i] = i;
  20.             _rank[i] = 0;
  21.         }
  22.     }
  23.  
  24.     void Union(int x, int y)
  25.     {
  26.         int xroot = Find(x);
  27.         int yroot = Find(y);
  28.  
  29.         if(_rank[xroot] > _rank[yroot])
  30.         {
  31.             parent[yroot] = xroot;
  32.         }
  33.         else
  34.         {
  35.             parent[xroot] = yroot;
  36.             if(_rank[x] == _rank[y])
  37.                 _rank[x] = _rank[x]+1;
  38.         }
  39.     }
  40.  
  41.     int Find(int x)
  42.     {
  43.         if(x != parent[x])
  44.         {
  45.             parent[x] = Find(parent[x]);
  46.         }
  47.         return parent[x];
  48.     }
  49. };
  50.  
  51. int main()
  52. {
  53.     disjointSet obj(5);
  54.     obj.Union(1,2);
  55.  
  56.     if(obj.Find(1) == obj.Find(1))
  57.         cout << "1" << endl;
  58.     else
  59.         cout << "0" << endl;
  60.     if(obj.Find(1) == obj.Find(3))
  61.     {
  62.         cout << "1" << endl;
  63.     }
  64.     else
  65.     {
  66.         cout << "0" << endl;
  67.     }
  68.     return 0;
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top