并查集刷题大全

并查集刷题大全

并查集的两种写法

路径压缩 均摊复杂度O(logn)

代码

查询int find(int x) return x==fa[x]?x:fa[x]=find(fa[x]);

修改x=find(x),y=find(y);if(x!=y) fa[x]=y;

按秩合并 均摊复杂度O(log(n))

每个节点一个秩,秩小的向秩大的合并,可以把秩看成树的深度

查询int find(int x) return x==fa[x]?x:fa[x];

修改x=find(x),y=find(y);if(rank[x]

路径压缩+按秩合并 均摊复杂度O(α(n)) α(n)可视作常数

其实光是路径压缩就优秀而且好写了,一般会路径压缩就可以了

路径压缩+按秩合并

按秩合并

路径压缩 No.1

进入正题,并查集能解决的问题有很多

​​1.将可以视为一个整体的东西合并​​(动态维护具有传递性的东西)

​​2.判断图的连通性​​

​​3.判断图中的环与大小​​

​​4.找左右第一个大于(小于)x的数​​

​​5.带边权的并查集查找x到fa[x]的距离​​

​​6.并查集不一定只有fa,还可能有多种情况​​(扩展域)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。