并查集详解及模板

1. 解决什么问题？

当题目最终要将数据分成若干个集合时，可往并查集的方向思考。并查集三个字拆开对应“合并”，“查找”，“集合”，这样就很好理解了。

【思路】

为了方便查找和合并，每个元素都有对应的代表元素，代表元素就是它所在集合里的所有元素的代表元素。

因此，要构建一个 father 数组 表示每个元素的代表元素。

2. 模板

1）构建集合/初始化

一开始每个元素就是自己的代表元素，后续根据题目要求进行合并，如果要求集合的个数也可以在此处表示。

也不一定写成函数，此处只是为了方便展示。

void build(int n)
{
    for (int i = 1; i < n; i++)
        father[i] = i;
    sets = n;
}

2）查找：递归思路

如果 i == father[i] ，则 i 为代表元素。

而当一个元素的 father 不是本身时，则再找 father 的 father，知道找到代表元素为止。

int find(int p)
{
    if (father[p] != p)
    {
        father[p] = find(father[p]);
    }
    return father[p];
}

3）合并

将代表元素合并，也就是相当于两个集合合成一个集合

 void set_union(int x, int y)
 {
     int fx = find(x);
     int fy = find(y);
     if (fx != fy)
     {
         father[fx] = fy;
         sets--;
     }
 }

3. 优化

一般的并查集用上面的模板就可以，如果想更快些，可以看下面的版本，但需要的空间会大些

1）扁平化

【思路】

因为 find 方法调用频繁，所以如果将递归的次数减少一些会大大优化时间复杂度

优化方法就是将同一代表元素的元素的 father 都改成代表元素(原先是通过递归来实现的)

【实现方式】

需要开一个栈来实现：栈来收集从该元素到代表元素沿途的元素，再将他们的 father 一一改成代表元素

而当下次再调用时，就可以只循环一次，找到它的 father。

int find(int i) {
    int size = 0;
    while (i != father[i]) {
        stack[size++] = i;
        i = father[i];
    }

    while (size > 0) {
        father[stack[--size]] = i;
    }
    return i;
}

2）小挂大

需要多开一个数组表示代表元素对应的集合的元素个数，记为 size 数组，初始化时全为1

两个集合合并表示为对应代表元素的 size 值小的加到大的上

void set_union(int × int y) 
{
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        // 小的挂在大的上
        if (size[f×] >= size[fy]) {
            size[f×] += size[fy];
            father[fy] = fx;
        } else {
            size[fy] += size[f×];
            father[fx] = fy;
        }
    }
}

PS：如果看模板不好理解，最好结合练习看会舒服很多

4. 练习

（1）模板题

链接：牛客_并查集的实现

（2）相似字符串组

链接：leet_839

【分析】

核心思路就是并查集，通过记录每个字符串的不同字符数找相似字符串，然后按并查集的思路合并，最终输出集合的个数。

【参考代码】链接

（3）情侣牵手

链接：leet_765

【分析】

情侣数一定是人数的一半，故只需开人数一半的集合即可，规定其 ID 对应除以2的数就是对应的情侣 ID；

那么每一次相邻两个元素合并就将其情侣 ID (可理解为代表元素)合并即可，因为在合并的函数中，属于相同集合的不用再进行操作，而只有不是属于一个集合的才减少集合的个数

【参考代码】链接