This is useful for Leetcode problems.

UnionFind.c

// free with free(arr);
static int* new_union(int n) {
  int* arr = malloc(sizeof(int)*n);
  for (int i=0; i<n; i++) arr[i] = i;
  return arr;
}

// Implements path compression
static int get_parent(int* arr, int i) {
  if (arr[i] == i) return i;
  const int parent = get_parent(arr, arr[i]);
  arr[i] = parent;
  return parent;
}

static void union_join(int* arr, int i, int j) {
  const int p1 = get_parent(arr, i);
  const int p2 = get_parent(arr, j);
  arr[p2] = p1;
}

static bool are_joined(int* arr, int i, int j) {
  return get_parent(arr, i) == get_parent(arr, j); 
}