Union-Find with Path Compression + Union by Rank

int[] parent, rank;
void init(int n) {
  parent = new int[n]; rank = new int[n];
  for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);  // path compression
  return parent[x];
}
void union(int x, int y) {
  int rx = find(x), ry = find(y);
  if (rx == ry) return;
  if (rank[rx] < rank[ry]) parent[rx] = ry;
  else if (rank[ry] < rank[rx]) parent[ry] = rx;
  else { parent[ry] = rx; rank[rx]++; }
}