Union find

Suyoung Lee

Mar 11, 2024

--

Share

#include<iostream>
using namespace std;
int parent[9]; 

int find(int x) {
 if (parent[x] == x) 
  return x;
 return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
 x = find(x);
 y = find(y); 
 if (x == y) return; 
 parent[y] = x; 
}

bool isUnion(int x, int y) { 
 x = find(x);
 y = find(y);
 if (x == y)
  return true;
 return false;
}

int main() {
 for (int i = 1; i <= 8; i++)
  parent[i] = i;

 merge(1, 2);
 merge(4, 5);
 merge(5, 6);
 cout << "are 2 and 4 in the same subset?\n" << isUnion(2, 4) << "\n"; 
 merge(1, 5);
 cout << "are 2 and 4 in the same subset? \n" << isUnion(2, 4) << "\n";
 return 0;
}