并查集超级易懂讲解

1、高级数据结构设计一一并查集及实现学习笔记(有趣篇)并查集的程序设计：二二二 pre .;二二二 ft二二二 x)/查找根节点二二二二=;whLle pre ； !=二； -=re i;0路径压缩9二二二 i=; TOC o 1-5 h z =二:;(i!=r):：=:己二；P-E 二=；i=;：/7返回根节点retire :;)1972Ld 二二口二二 壬,二二二 y):77判断by是丐连谑77如果已经连通，就K巨管了/7如果木连通就把主仁所在的连通分支合并起来二二二 fj= a, j = bo如果最后fnn1 = 1说明是唯一的情况，输出该情况，否则输出 “no” （多解算no）注意点：这题

2、的m, n1, n2都有可能出现0，可以特殊处理，也可以一起处理。按上面的dp写法，fij可能会很大，因为n可以达到三位数。其实我们关心的只是fij等于0，等 于1，大于1三种情况，所以当fij 1时，我们都让它等于2即可。POJ 2912 Rochambeau （难）http:/acm.pki i.edi /Ji idgeOnline/problem?id=2912Baidu Star 2006 Preliminary的题目，感觉出的很好，在并查集题目中算是较难的了。其实这题跟食物链完 全一个磨子，同样三类食物，同样的互相制约关系。所以食物链代码拿过来改都不需要改。但这题有个 judge，他

3、可以出任意手势。于是我们的做法是，枚举每个小孩为judge，判断他为judge时在第几句话出 错erri（即到第几句话能判断该小孩不是judge）。如果只有1个小孩是judge时全部语句都是正确的，说明该小孩是judge，那么判断的句子数即为其他小 孩的erri的最大值。如果如果每个小孩的都不是judge（即都可以找到出错的语句），那么就是impossibleo多于1个小孩是judge时没有找到出错的语句，就是Can not determineoZOJ 3261 Connections in Galaxy War HYPERLINK http:/acm http:/acm.7/onlineju

4、dge/showProblem.do?problemId=3563nuaa 1087联通or不连通 HYPERLINK /acmhome/problemdetail.do?&method=showdetail&id=1087 /acmhome/problemdetail.do?&method=showdetail&id=1087两题做法差不多，都是反过来的并查集题目，先对边集排序，然后把要删去的边从二分在边集中标记。 然后并查集连接没有标记的边集，再按查询反向做就可。第一题合并结点时按照题目要求的优先级合并 即可。这里介绍的并查集题目，主要都是处理些集合之间的关系（这是并查集的看家本领），至于

5、并查集还有 个用处就在求最小生成树的Kruskal算法中，那个是图论中求最小生成树的问题（一般这个难点不在于并 查集，它只是用于求最小生成树的一种方法），就不在这里赘述了分享来自Tina_Z_Y和czyuan感谢两个牛人!本文采用BY-NC-SA协议进行授权，转载请注明：转高级数据结构设计一一并杳集及实现学习笔记（有趣篇）I ACShiryus ACM +维基百科/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86并查集维基百科，自由的百科全书跳转到：导航，搜索并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表

6、示。目录隐藏1主要操作1.1合并两个不相交集合1.2判断两个亓素是否属于同一集合2并杳集的优化2.1路径压缩2.2 Rank 合并3源代码4时间及空间复杂度5应用编辑主要操作需要注意的是，一开始我们假设元素都是分别属于一个独立的集合里的。编辑合并两个不相交集合操作很简单：先设置一个数组Fatherx，表示x的“父亲”的编号。那么，合并两个不相交集合的方法就是，找到其中一个集合最父亲的父亲（也就是最久远的祖先），将另外一个集合的最久远的祖先的父亲指向它。Pascal 代码：function Union(x,y:integer):boolean;(其中 GetFather 是下面将讲到的操作var

7、 fx,fy : integer;beginfx := getfather(x);fy := getfather(y);If fx=fy then exit(false)else Union:= true;fatherfx := fy;(指向最祖先的祖先end;C语言代码表示形式：void Union(int x,int y)(fx = getfather(x);fy = getfather(y);if(fy!=fx)fatherfx=fy;编辑判断两个元素是否属于同一集合仍然使用上面的数组。则本操作即可转换为寻找两个元素的最久远祖先是否相同。可以采用递归实现。Pascal 代码：Functi

8、on Same(x,y:integer):boolean;beginif GetFather(x)=GetFather(y) thenexit(true) elseexit(false);end;C代码：bool same(int x,int y)(return getfather(x)=getfather(y);/*返回true表示相同根结点，返回false不相同*/编辑并查集的优化刚才我们说过，寻找祖先时采用递归，但是一旦元素一多起来，或退化成一条链，每次GetFather都将会使用O(n)的复杂度，这显然不是我们想要的。对此，我们必须要进行路径压缩，即我们找到最久远的祖先时“顺便”把它的

9、子孙直接连接到它上面。这就是路径压缩了。使用路径压缩的代码如下：Function getfather(v:integer):integer;beginif (fatherv=v) thengetfather:=velsebeginfatherv:=getfather(fatherv);(路径压缩getfather:=fatherv;end;end;int getfather(int v)(if (fatherv=v)return v;else(fatherv=getfather(fatherv);/ 路径压缩return fatherv;Procedure Initialize;vari:in

10、teger;beginfor i:=1 to maxv doFatheri:=i;end;Function GetFather(v:integer):integer;beginif Fatherv=v thenexit(v) elseFatherv:=getfather(fatherv);(路径压缩exit(Fatherv);end;编辑Rank合并合并时将元素所在深度低的集合合并到元素所在深度高的集合。function judge(x,y:integer):boolean;var fx,fy : integer;begin fx := getfather(x); fy := getfathe

11、r(y);If fx=fy then exit(true) else judge := false;if rankfxrankfy thenfatherfy := fx else beginfatherfx := fy;if rankfx=rankfy then inc(rankfy);end;end;初始化：fillchar(rank,sizeof(rank),0);C语言代码：合并时将元素所在深度低的集合合并到元素所在深度深的集合。void judge(int x ,int y)( fx = getfather(x);fy = getfather(y);if (rankfxrankfy)fatherfy = fx;else( fatherfx = fy;if(rankfx=rankf