路径压缩

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_36670529/article/details/102455149

并查集中的find函数,可以用于查找某个节点的父亲节点,某些情况下,我们为了加快查找的速度,就要用到路径压缩的写法。

int find(int x)
{
int tmp,son;
son=x;
while(x!=pra[x])
x=pra[x];
while(son!=x)
{
tmp=pra[son];
pra[son]=x;
son=tmp;
}
return x;
}

我们一开始找到了x的父亲节点,之后,我们随着(X--->X的祖先)这条路,一直把这条路上的所有节点的父节点都标记为祖先节点。从而加快了查找的速度。

################################################################

有关并查集join函数的新认识:

1.如果不考虑树的整体结构,

void join(int b1,int b2)//两颗树的合并操作
{
int x=find(b1);//找到树b1的根节点
int y=find(b2);//找到树b2的根节点
if(x!=y)//如果两棵树不同根
pra[y]=x;//链接两棵树
}

2.需要考虑到树的整体结构:

void join(int b1,int b2)//两颗树的合并操作
{
int x=find(b1);//找到树b1的根节点
int y=find(b2);//找到树b2的根节点
if(x!=y)//如果两棵树不同根
pra[b2]=b1;//链接两棵树
}

其他东西:

1.FIND函数能查找子节点的祖先节点

2.采用了路径压缩的FIND函数、JOIN函数可以修改子节点的父亲节点。

######################################################

路径压缩的使用前提是不考虑树的整体结构,也就是说FIND函数必须采用第一种写法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • c++ int,unsigned int混合表达式类型转换

    int和unsigned int的混合表达式,计算时会将int转换为unsigned int。普通情况下会将范围小的隐式转换为范围大的,但对于int和unsig...

    于小勇
  • 矩阵求导、几种重要的矩阵及常用的矩阵求导公式

    原文链接:https://blog.csdn.net/daaikuaichuan/article/details/80620518

    于小勇
  • 平衡二叉树(AVL树)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    于小勇
  • 程序员面试金典 - 面试题 16.07. 最大数值(位运算求max)

    编写一个方法,找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。

    Michael阿明
  • 洛谷P3355 骑士共存问题

    题目描述 在一个 n*n个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入 ? 对于给定的 n*n 个方格的国...

    attack
  • C++创建动态库C#调用(二)----回调函数的使用

    上一篇《C++创建动态库C#调用》我们练习了C++写的动态库用C#的调用方法,后来研究回调函数这块,就想练习一下回调函数的使用,学习并巩固一下,话不多说,我们直...

    Vaccae
  • P2279 [HNOI2003]消防局的设立

    题目描述 2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路...

    attack
  • [HAOI2006]受欢迎的牛 Tarjan

    本弱一开始想就是所有点能到达一个点的点就符合条件,那么就反向建边,对于某个点能跑遍所有点就ans++.不过TLE了最后两个测试点(过了18个测试点hhhhh)。

    用户2965768
  • More is better(并查集)

    #include<stdio.h> #include<string.h> const int MAXN=10000010; int father[MAXN],h...

    用户1624346
  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack

扫码关注云+社区

领取腾讯云代金券