【图论】并查集的学习和使用
目录
并查集是什么？
举个例子
组成
父亲数组：
find函数：
union函数：
代码实现：
fa[] 初始化code:
find code：
递归实现:
非递归实现:
union code :
画图模拟：
路径压缩：
路径压缩Code：
并查集是什么？
是一种树形的数据结构，一般用来处理集合的合并，查询操作。
举个例子
告诉你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];
}