并查集模板

路径压缩：

int find(int x) {
    if (x != fa[x]) {
        int tmp=fa[x];
        fa[x]=find(fa[x]);
        d[x]=(d[x]+d[tmp])%2;//自定义边权压缩
    }
    return fa[x];
}

按秩合并（无序）：

void Union(int x,int y) {
    int rootx=find(x),rooty=find(y);
    if (rank[x]>rank[y]) fa[rooty]=x;
    else {
        fa[rootx]=y;
        if (rank[x]==rank[y]) rank[y]++;
    }
}