dsa/graphs/dsu | desc: disjoint set union dsu

dsu.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int arr[N];

void initialze(int n){
  for (int i = 0; i < n; i++) arr[i] = -1;
}

int _find(int key){
  if (arr[key] < 0) return key;
  return arr[key] = _find(arr[key]); // Path compression
}

void _union(int a, int b){
  int par_a = _find(a);
  int par_b = _find(b);
  if (par_a == par_b) return;
  if (arr[par_a] > arr[par_b]) swap(par_a, par_b);
  arr[par_a] += arr[par_b]; // Update size
  arr[par_b] = par_a; // Update parent of B
}