一、什么是并查集
什么是并查集?字面意思把一堆东西 合并 、 查找
二、并查集讲解前置知识点
1.可以把并查集的实现理解为在合并几棵树
2.需要用到fa数组,fa[i]表示i的父节点的编号,如果为i则i为祖宗节点
三、查找
这个部分要实现找到k的祖宗节点,那么很简单只要在开头判断自己是否是祖宗节点,是,返回自己的值,不是,继续往上找直到找到祖宗节点为止
int find(int k) { if(fa[k]==k) return k; else return find(fa[k]); }
四、合并
要把a合并到b很简单只要fa[a]=b就可以了(要注意不返回值的函数一定要是void类型)
void b(int a,int b) { fa[a]=b; }
五、路径压缩
一般的并查集是这样的
那我们不妨每次连接a b时,连接他们的祖宗,那么find的复杂度将会缩小,就会变成这样
并的程序:
void b(int a,int b) { fa[find(a)]=find(b); }
标签:int,查集,节点,fa,祖宗,find From: https://www.cnblogs.com/wjk53233/p/17110518.html