首页 > 其他分享 >并查集

并查集

时间:2023-02-10 22:34:36浏览次数:47  
标签:int 查集 节点 fa 祖宗 find

一、什么是并查集

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

二、并查集讲解前置知识点

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

相关文章

  • 并查集
    并查集大佬笔记如下:通俗易懂https://zhuanlan.zhihu.com/p/93647900并查集是什么?主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:合并:把......
  • 【YBT2023寒假Day8 C】图论题(图论)(并查集)(线段树合并)
    图论题题目链接:YBT2023寒假Day8C题目大意给你一个无向图,然后你会一直操作直到无法操作,每次找出一个满足条件的三元组(a,b,c),满足a<b<c,a,b与a,c之间有边,b,c之间没......
  • 2021 年百度之星·程序设计大赛 - 初赛二 1003 魔怔(并查集,联通性,欧拉回路)
    problemsolution发现除了起点和终点,剩下所有点周围的边都会被恰经过偶数次,所以这些点初始连向了偶数条白边。考虑由白边连接形成的图,每个连通块中度数为奇数的点一定为偶数......
  • 【Baltic2003】【BZOJ1370】Gang团伙(并查集,拆点)
    problem给定n个人朋友的朋友是朋友,敌人的敌人是朋友朋友之间组成一个团伙,求团伙数solution将每个点x拆成两个:x和x+n(分别表示x的朋友和敌人)如果x和y是朋友,就将x和y合并如果x......
  • 并查集判断(DSU)二分图
    并查集(DSU)判断二分图题目链接二分图性质当且仅当图中不存在奇数环偶数环时可以扭成这样但奇数环则不可以从染色法的角度来考虑:假设一个二分图中左边标号为1......
  • 种类并查集 洛谷 P2024 食物链
    题目描述动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道......
  • 带权并查集 区间统计
    带权并查集区间统计例题:​​HDU ZjnuStadium​​(模板)​​HDU3038HowManyAnswersAreWrong​​与普通并查集不同是新增加一个属性:dist[a]:表示a到父亲节点的距离操......
  • 【bzoj4668】冷战 (并查集按秩合并+朴素LCA)
    题目描述1946年3月5日,英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”,正式拉开了冷战序幕。美国和苏联同为世界上的“超级大国”,为了争夺世界霸权,两国及其盟国......
  • POJ 1611--The Suspects【并查集水题】
    TheSuspectsSevereacuterespiratorysyndrome(SARS),anatypicalpneumoniaofunknownaetiology,wasrecognizedasaglobalthreatinmid-March2003.Tominim......
  • poj 1182 食物链(并查集)
    食物链TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 33156 Accepted: 9626Description动物王国中有三类动物A,B,C,这三类动物的食物链构成......