首页 > 其他分享 >关于并查集的感受

关于并查集的感受

时间:2023-10-22 13:11:48浏览次数:30  
标签:issame 感受 查集 成环 关于 集合 join 节点

什么情况下2个节点还没加入一个集合就已经在一个集合了?就说明如果把这2个节点画进图里连起来,那么一定构成了一个环。

举个简单的栗子

 

对于join函数,只要加入了2个节点,那么至少这两个节点就构成了1个集合,如果还没加入它们就以及有同一个根节点了那么就说明对应的图里存在环,如果连接这两个节点那么就能形成环。

另外,对于并查集来说,join就是告诉你把n,v节点加入到一个集合里,这个集合最小就是n,v。然后issame就是告诉你n,v,节点是不算属于1个集合。
而且由于每次join和issame都要findf,那么就是会把那个节点及其父节点及其父节点直到根节点全部挂载在根节点上,当然实现是father实现的,不过这个结构是抽象出来的。也叫路径压缩可以快速判断节点的根节点。

一个节点的入度就是指向这个节点的边的个数,出度就是从这个节点出去的边的个数。
对于并查集的操作之一检查树是否成环,就是遍历每一个边然后先判断是否issame,然后再join。一旦issame=1,就说明有成环。当然也可以跳过某一个边去检查,毕竟原理一样,遇到continue了就行。 注意::这里的环是指无向环。

总之 并查集一般用于集合、无向图,可以把两个元素加入1个集合,也可以检查2个元素是否属于1个集合,也可以检查树是否成环。一般情况下不适用于有向图(除了力扣那个冗余连接2它太特殊了首先它本身就是一个树只不过加了一条边而已,有一个情况下,那条边就是指向根节点的,这种情况下等同于无向边,我是这么想的。)

 

 

标签:issame,感受,查集,成环,关于,集合,join,节点
From: https://www.cnblogs.com/NiShu7777/p/17780322.html

相关文章

  • 关于多项式右复合三次函数的一些思考
    一个模多项式模数做\(f(ax^3+bx^2+cx+d)\)的可能好实现一些的方法。感觉就是把EI老师的某博客展开写了。理性愉悦。确实常数不是很小,至少我这个做法是这样的。首先处理一下,把任意的三次函数转化成特殊三次函数。可以拆成\((x+d)\circax\circF\),其中\(F=x^3+......
  • 【Shell篇】关于如何在.cshrc中自动设置terminal中prompt提示符以及title?
    废话不多说,直接上代码:setprompt="%{\033]0;%n@%m:%/\007%}%n@%m:%/>"aliascd'cd\!*;setprompt="%{\033]0;%n@%m:%/\007%}%n@%m:%/>"'第一行代表当本.cshrc执行时会将prompt以及title设置成用户自定义的格式;第二行代表用户每次执行cd命令切换路径时,prompt以及title......
  • 关于原始typescript实现todolist(装饰器模式)
    前言我是歌谣最好的种树是十年前其次是现在今天继续给大家带来的是原始typescript的讲解环境配置npminit-yyarnaddvite-D修改page.json配置端口{"name":"react_ts","version":"1.0.0","description":"","main":"index.......
  • 关于多核开发的技术要点
    #推荐两个支持多核ARM开发的集成开发环境:NucleusEDGE:这是AcceleratedTechnology公司基于Eclipse平台的集成开发环境,集成了项目管理器、代码编辑器、编译工具、调试器和模拟器等工具,具有简单易用的用户界面。其突出优点包括多处理器调试能力、实时跟踪、代码覆盖率分析、......
  • 关于图的一点东西
     自环的应用比如说在一个网页界面,我可以点击一个跳转到当前业面的链接,形成自环。多重边的应用比如飞机航班,一个地方到另一个地方可以有多条航线,这些航线的属性比如价格,时间等会有不同。......
  • 关于JAVA项目中的常用的异常处理情况
    JAVA项目中的常用的异常处理情况总结   在Java应用程序开发中,异常处理是至关重要的,因为它可以帮助您的程序应对各种不可预测的情况和错误。无论是在开发新项目还是在维护现有项目时,了解如何有效地处理异常是确保您的应用程序稳定性和可靠性的关键。本文将深入探讨Java项......
  • 点关于直线对称、线关于线对称的终极公式
    点关于直线对称设直线\(l:Ax+By+C=0\)坐标平面内一点\(M(x_0,y_0)\)他关于该直线的对称点为\(N(x,y)\)则该对称点满足:\(x=x_0-2A\frac{Ax_0+By_0+C}{A^2+B^2}\)\(y=y_0-2B\frac{Ax_0+By_0+C}{A^2+B^2}\)直线关于直线对称对称轴方程\(Ax+By+C=0\)被反射直线方程\(l_......
  • 关于三角形的四种心(外心,内心,重心,垂心)
    外心三条边垂直平分线的交点为外心。到三顶点距离相等内心三条内角平分线的交点为内心。到三条边的距离相等同时是内切圆的圆心重心三条中心的交点为重心同时是物理意义上的重心公式:\(G(x_0,y_0),x_0=\frac{x_1+x_2+x_3}{3},y_0=\frac{y_1+y_2+y_3}{3}\)垂心......
  • 关于Gorm配合Postgim的使用
    碰到一个问题,项目中需要引入坐标系统,而数据库选用是postgresql,那么理所当然的想到的就是用postgim插件,关于这个插件的使用,我们建议使用docker,doccker-compose配置如下version:'3.1'services:db:image:postgis/postgis:16-3.4restart:alwaysenvironment:......
  • 关于 RabbitMQ 做消息推送的一点记录
    先说需求,需求是很简单的,也就是假设有10w+的用户,每个用户都需要维护一个长链,那么就不可能单机,就需要分布式,而分布式的就需要确保精确推送,确保用户A的数据确实能被推送到用户A连接的机器那,所以一个主要思路就是用消息队列的routingkey的逻辑去做确保所有节点订阅了一个topic,并持有......