Union Find

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

void union(int u, int v) {
    u = find(u), v = find(v);
    if (rk[u] < rk[v]) swap(u, v);
    parent[v] = u;
    rk[u] = max(rk[u], rk[v] + 1);
}