高级数据结构2—并查集

问题提出：

有N个同学，他们之间有些是朋友，有些不是。"友谊"是可以传递的，例如A与B是朋 友，B与C是朋友，那么A与C也是朋友;朋友圈就是完成"友谊"传递后的一组朋友。 给定N*N的矩阵代表同学间是否是朋友，如果M[i][j] = 1代表第i个学生与第j个学生是朋 友，否则不是。求朋友圈的个数。

示意图
这个问题可以用并查集解决：
并查集(Union Find)，又称不相交集合(Disjiont Set)，它应用于N个元素的集合求并(union)与查询(find)问题，在该应用场景中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。虽然该问题并不复杂，但面对极大的数据量时，普通的数据结构往往无法解决，并查集就是解决该种问题最为优秀的算法。 示意图
并查集的实现方式有两种：数组实现和森林实现；

数组实现方式 数组实现方式

从上面可以看出，find操作的时间复杂度为O(1)。而union操作时间复杂度为O(n)。对于海量数据而言，这样实现方式还不是最佳的。

并查集森林实现方式

使用森林存储集合之间的关系，属于同一集合的不同元素，都有一个相同的根节点 ，代表着这个集合。 当进行查找某元素属于哪个集合时，即遍历该元素到根节点，返回根节点所代表的集 合;在遍历过程中使用路径压缩的优化算法，使整体树的形状更加扁平，从而优化查 询的时间复杂度。 当进行合并时，即将两颗子树合为一颗树，将一颗子树的根节点指向另一颗子树的根 节点;在合并时可按子树的大小，将规模较小的子树合并到规模较大的子树上，从而使 树规模更加平衡，从而优化未来查询的时间复杂度。

示意图 数据结构

class DisjoinSet
{
private:
    std::vector<int> id;//用来存放该结点的父亲结点是哪一个
    std::vector<int> size;//记录当前元素所在集合的大小
    int count;//并查集里集合的数量，初始值为元素的个数
pubic:
DisjoinSet(int n)
    {
        for(int i=0;i<n;i++)
        {
            id.push_back(i);
            size.push_back(1);
        }
        count = n;
    }
};

路径压缩优化是并查集最简单、也是非常有效的一个优化。
在执行find(a)的过程中，路径压缩优化会将从a到d路径上的所有点都指向有根树的根，也就是d。这么做的好处在于：通过这样的处理，能将有根树的高度尽可能降低，下次再进行查询或合并操作的时候时间开销就更小了。路径压缩优化实现起来并不复杂，在find函数中，当发现当前结点不是根结点时，会不断的递归求解，并将结果直接作为返回值返回了。

示意图 查找

int find(int p)
    {
        while(id[p]!=p)
        {
            id[p]=id[id[p]];//路径压缩，把该点父节点设定为父节点的父节点
            p=id[p];
        }
        return p;
    }

合并

void unionMen(int p,int q)
    {
        int p_p = find(p);
        int q_p = find(q);
        if(p_p==q_p)return;
        if(p_p!=q_p)
        {
            if(size[q_p]<size[p_p])
                {
                    id[q_p]=p_p;
                    size[p_p]+=size[q_p];
                }
            else
            {
                id[p_p]=q_p;
                size[q_p]+=size[p_p];
            }
            count--;
        }
    }

完整代码可以戳➡️我的GitHub;
希望大家一起进步～