并查集-6ren

并查集

转载作者：我是一只小鸟更新时间：2023-02-10 22:31:06

1、什么是并查集。

什么是并查集？字面意思把一堆东西合并、查找。

2、并查集讲解前置知识点。

1.可以把并查集的实现理解为在合并几棵树。

2.需要用到fa数组,fa[i]表示i的父节点的编号，如果为i则i为祖宗节点。

3、查找。

这个部分要实现找到k的祖宗节点，那么很简单只要在开头判断自己是否是祖宗节点，是，返回自己的值，不是，继续往上找直到找到祖宗节点为止。

                          
                            int
                          
                           find(
                          
                            int
                          
                          
                             k)
{
    
                          
                          
                            if
                          
                          (fa[k]==k) 
                          
                            return
                          
                          
                             k;
    
                          
                          
                            else
                          
                          
                            return
                          
                          
                             find(fa[k]);
}

4、合并。

要把a合并到b很简单只要fa[a]=b就可以了（要注意不返回值的函数一定要是void类型）。

5、路径压缩。

一般的并查集是这样的。

。

那我们不妨每次连接a b时，连接他们的祖宗，那么find的复杂度将会缩小，就会变成这样。

。

并的程序:

                          
                            void
                          
                           b(
                          
                            int
                          
                           a,
                          
                            int
                          
                          
                             b)
{
    fa[find(a)]
                          
                          =
                          
                            find(b);
}

。

最后此篇关于并查集的文章就讲到这里了,如果你想了解更多关于并查集的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。