并查集 将集合在逻辑上表示为树结构。

void Initial() {
    for(int i=0; i<n; i++) {
        father[i]=i;
        height[i]=0;
    }
    return ;
}

int Find(int x) {                                                                        //路径压缩
    if(x!=father[x]) {
        father[x]=Find(father[x]);
    }
    return father[x];
}

void Union(int x,int y) {                                                           //合并集合
    x=Find(x);
    y=Find(y);
    if(x!=y) {
        if(height[x]>height[y]) {
            father[y]=x;
        } else if(height[x]<height[y]) {
            father[x]=y;
        } else {
            father[y]=x;
            height[x]++;
        }
    }
    return ;                                                                        //防止成环