【图论】并查集的学习和使用

并查集是什么？

是一种树形的数据结构，一般用来处理集合的合并，查询操作。

举个例子

告诉你1的父节点是2 2的父节点是3 4的父节点是5 6没有父节点 那么可以画出

三个集合，或者说是树 。然后我们一般用并查集判断：①有几棵树 也就是有几个集合 ② 两个点是否同属于一个集合 ③一个点是不是属于这棵树

组成

主要是通过一个父亲数组和一个find函数、一个union函数实现的。

父亲数组：

记录一个节点的父结点 初始化为自己 也就是一开始自己就是自己的父结点 自己单独属于一个集合

find函数：

根据邻接关系 找到一个结点的根结点 如果两个结点的通过find函数寻找出来的结点相同 则同属一个集合

union函数：

遍历邻接关系时 将两个邻接的结点父亲数组更新的作用 具体来说 判断若两个结点通过find函数寻找出来的根节点不相同 也就是不属于一个集合 则将一个集合并入另一个集合 通过把前一个结点的根节点 的父亲数组 标记为第二个结点的根节点 则两个集合就合并了

代码实现：

fa[] 初始化code:

for(int i=0;i<n;++i)
       fa[i]=i;

find code：

递归实现:

int finds(int a){
    if(a!=fa[a]){
        fa[a]=finds(fa[a]);
    }
    return fa[a];
}

非递归实现:

int finds(int a){
    while(a!=fa[a]){
        a=fa[a];
    }
    return fa[a];
}

详细解释：一个结点 只有父结点是自己 也就是fa[]数组中是自己 才能称为根节点 finds函数就是判断一个结点是否为根结点 如果不是 就继续向上finds他的父节点 看是不是根结点 直到找到根节点 返回 这个根节点可以称之为一个集合的标志

union code :

void unions(int x,int y){
    int fx=finds(x);
    int fy=finds(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}

详细解释：unions函数是用于遍历邻接关系时 更新集合关系。传入两个结点 找到他们的根节点 也就是他们所属集合的标志 判断是否相同 也就是判断是否从属于一个集合 如果不属于一个集合 则把第一个集合的根节点 的父亲结点 更新为 第二个集合的根节点。也就是把第一个集合和第二个集合合并 并且根节点保留为第二个集合的根节点 。

画图模拟：

①我们要判断两个点是否属于一个集合 只要用find函数即可

②我们要判断共有几个集合 只要看fa数组中有几个 i=fa[i]即可 因为fa[i]等于i 代表是集合里的根结点 一个集合只有一个根结点 所以根结点数即为集合数量

路径压缩：

可以观察到 每次调用find函数都需要经历一串长长的递归 这正是函数时间花费的地方 考虑优化的地方 我们可以直接把fa[i]数组标记为i结点所属集合的根节点 也就是把整条路径上的fa[i]数组都标记为根节点 按上面画图的例题来说 就是把fa[1] fa[3] fa[4] 全部标记为4 这样调用find函数的时候就特别快，一步到位。要想完成这个操作 只要在find函数后加一步 每次find的时候 找到了根节点的值 保存 再用一个while循环向上查找 把整条路径上的结点的fa[]值都更新为找到的根节点

路径压缩Code：

int new_finds(int a){
    int aa=a;//保存一下查找的点 也就是路径的底部
    if(a!=fa[a]){
        fa[a]=finds(fa[a]);//找到了根节点
    }
    while(aa!=fa[a]){//向上更新整条路径
        int temp=fa[aa];//先存储路径的下一个点
        fa[aa]=fa[a];//路径压缩一个
        aa=temp;//再压缩下一个点
        
    }
    return fa[a];
}