c++ 初级并查集详解

2025-04-05 12:09:53

1、初始化:一开始,每一个元素都是一个集合,打个比方,每个人所在的 "家族" 只有他一个人。我们还需要一个f 数组,里面存的是他的 “父亲” 的编号,初始值为f[1]=1,f[2]=2……f[n]=n,如图

c++ 初级并查集详解

2、find函数:find(a)是用来查找a的“祖先”的,例如,我们要查找 a的祖先,就要去找a 的父亲的父亲……,直到有个人 b,他的父亲就是他自己,那么 b就是 a的祖先代码如下:int find (int x){ if(f[x] == x) return x;//如果x的父亲就是他自己,则x为a的祖先 else return find (f[x]);//否则a的祖先 就是a的父亲的祖先}int x=find(a);

3、union函数:union(a,b)就是合并 a,b这两个人所在的家族,只需要把 a的祖先的父亲 指向 b的祖先如何合并?我们设u=find(a),v=find(芟鲠阻缒b) , 只要将 u,v其中一个人的父亲编号指向另外一个人就行了,例如f[u]=v代码如下:void Union (int a,int b)//因为union是c++的保留字,所以只好大写u{ int u= find(a), v= find(b);//寻找a,b的祖先 f[u]=v;//合并家族}Union (a,b);

c++ 初级并查集详解

4、在合并的时候还有一个注意点:为什么不能直接把 a的父亲指向 b?因为这样并不能合并完全,a的父亲,a 的父亲的父亲……,都不能合并到b 的家族里(想一想,为什么?),如图

c++ 初级并查集详解

5、查询两个元素是否在同一集合里:查询 a,b是否在同一集合里,就是看他们的祖先是否相等,若相等则在同一集合里,否则就不在代码如下:if( find(a) == find(b) ) cout<<"Y\n"; //如果祖先相等就输出“Y”else cout<<"N\n"; //否则输出“N”

6、例题:至此,你应该对并查集有了初步的了解,是时候上例题了题目描述如题,现在有一个并查集,你需要完成合并和查询操辑湃形傥作。输入输出格式输入格式:第一行包含两个整数N、M,表示共有N个元素和M个操作。接下来M行,每行包含三个整数Zi、Xi、Yi当Zi=1时,将Xi与Yi所在的集合合并当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N输出格式:如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N其实,这道题目就是把上面几个步骤综合在一起,代码如下

c++ 初级并查集详解

7、并查集的路径压缩路径压缩,顾名思义,就是将本来要很多步完成的事情压缩成一步因为我们每次find(a) 都要消耗 O (a的层数) 的时间,如果数据构造成一条链,则每次find 都需要O(n) 的时间,这是我们不希望看到的所以,我们可以把 f 数组的性质改变一下 f[a] 指向的编号变为a 的祖先代码该怎么写呢?我们只需要在 find 函数里把return find (f[x]);变成return f[x]=find(f[x]);就可以了这样每一次find 都会使路径上的每个f[x] 指向x 的祖先,每一次 find 也就只需要1 步就行了(除非被合并过,那也只需要 2 步),这就是路径压缩的实质

c++ 初级并查集详解
声明:本网站引用、摘录或转载内容仅供网站访问者交流或参考,不代表本站立场,如存在版权或非法内容,请联系站长删除,联系邮箱:site.kefu@qq.com。
猜你喜欢