fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. class UnionFind {
  8.   private:
  9.     int m_Size;
  10.     vector<int> m_ComponnetSize;
  11.     vector<int> m_Parent;
  12.     int m_NoOfComponents;
  13.  
  14.     int Find(int p) {
  15.       /*
  16.       inr root = p;
  17.       while(root != parent[root]) {
  18.         root = parent[root];
  19.       }
  20.  
  21.       while(p != root) {
  22.         int next = m_Parent[p];
  23.         m_Parent[p] = root;
  24.         p = next;
  25.       }
  26.       return root;
  27.       */
  28.       if(m_Parent[p] != p) {
  29.         m_Parent[p] = Find(m_Parent[p]);
  30.       }
  31.  
  32.       return m_Parent[p];
  33.     }
  34.  
  35.   public:
  36.     UnionFind(int size) {
  37.       m_NoOfComponents = size;
  38.       m_Size = m_NoOfComponents;
  39.       m_ComponnetSize = vector<int>(size);
  40.       m_Parent = vector<int>(size);
  41.       for(int i = 0; i < size; i++) {
  42.         m_Parent[i] = i;
  43.         m_ComponnetSize[i] = 1;
  44.       }
  45.     }
  46.  
  47.     int Size() {
  48.       return m_Size;
  49.     } 
  50.  
  51.     int Components() {
  52.         return m_NoOfComponents;
  53.     }
  54.  
  55.     void Union(int p, int q) {
  56.       int rootP = Find(p);
  57.       int rootQ = Find(q);
  58.       if(rootP == rootQ) return;
  59.       cout << rootP << ' ' << rootQ << endl;
  60.       if(m_ComponnetSize[rootP] < m_ComponnetSize[rootQ]) {
  61.           m_ComponnetSize[rootQ] += m_ComponnetSize[rootP];
  62.           m_Parent[p] = rootQ;
  63.       }
  64.       else {
  65.           m_ComponnetSize[rootP] += m_ComponnetSize[rootQ];
  66.           m_Parent[p] = rootP;
  67.       }
  68.       m_NoOfComponents--;
  69.     }
  70.  
  71.     void PrintUF() {
  72.       for(int i = 0; i < m_Size; i++) {
  73.         cout << Find(i) << ' ';
  74.       }
  75.       cout << endl;
  76.     }
  77. };
  78.  
  79.  
  80. int main() {
  81.   UnionFind uf(5);
  82.   uf.Union(4,3);
  83.   uf.PrintUF();
  84.   uf.Union(2,1);
  85.   uf.PrintUF();
  86.   uf.Union(1,3);
  87.   uf.PrintUF();
  88. }
Success #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4 3
0 1 2 3 4 
2 1
0 1 2 3 4 
1 3
0 1 2 3 4
https://ideone.com/wg5iug
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!