题解 | 【模板】并查集

先贴一个板子，感觉这个算法非常精妙。

//并查集
//初始化
for(int i=1;i<=n;i++){
    p[i] = i;
    length[i]=1;
}

// 查看祖宗编号，即集合编号。
static int find(int x){
    if(x!=p[x]) p[x] = find(p[x]);//并查集+压缩路径
    return p[x];
}
// 合并集合
static void merge(int x,int y){
    //length[find(y)]+=getLength(x); 维护集合内的元素个数。
    //d[px] = d[y]-p[x];
    p[find(x)] = find(y);//x所在集合 接到y集合后了。
}
//判断两元素是否在同一集合。
static boolean isSameSet(int x,int y){
    if(find(x)==find(y)) return true;
    else return false;
}
// 获取集合内元素的个数
static int getLength(int x){
    return length[find(x)];
}

图示：

假如，两个集合要合并，那么只需要将x的祖宗直接指向y的祖宗。这也解决了暴力做法，两个较大集合不好合并的问题，从原来的O(n)复杂度，降到了O(1)。