并查集模板

int find(int x) {
    int p = x, t;
    while (fa[p] >= 0) p = fa[p];
    while (x != p) {
        t = fa[x];
        fa[x] = p;
        x = t;
    }
    return x;
}
void union(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return;
    if (fa[x] < fa[y]) {
        fa[x] += fa[y];
        fa[y] = x;
    } else {
        fa[y] += fa[x];
        fa[x] = y;
    }
}