PASCAL并查集及其应用.docx
《PASCAL并查集及其应用.docx》由会员分享，可在线阅读，更多相关《PASCAL并查集及其应用.docx（24页珍藏版）》请在冰点文库上搜索。
PASCAL并查集及其应用
并查集及其应用
一、引例
例一、亲戚（relation.pas,relation.c,relation.cpp）
问题描述：
或许你并不知道，你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。
如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。
在这种情况下，最好的帮手就是计算机。
为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。
从这些信息中，你可以推出Marry和Ben是亲戚。
请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。
输入输出格式：
输入由两部分组成。
第一部分以N，M开始。
N为问题涉及的人的个数（1N20000）。
这些人的编号为1,2,3,…,N。
下面有M行（1M1000000），每行有两个数ai,bi，表示已知ai和bi是亲戚。
第二部分以Q开始。
以下Q行有Q个询问（1Q1000000），每行为ci,di，表示询问ci和di是否为亲戚。
对于每个询问ci,di，输出一行：
若ci和di为亲戚，则输出“Yes”，否则输出“No”。
输入输出样例：
relation.in
107
24
57
13
89
12
56
23
3
34
710
89
relation.out
Yes
No
Yes
问题分析：
将每个人抽象成为一个点，数据给出M个边的关系，两个人是亲戚的时候两点间有一条边。
很自然的就得到了一个N个顶点M条边的图论模型，注意到传递关系，在图中一个连通块中的任意点之间都是亲戚。
对于最后的Q个提问，即判断所提问的两个顶点是否在同一个连通块中。
用传统的思路，可以马上反应过来，对于输入的N个点M条边，找出连通块，然后进行判断。
但这种实现思路首先必须保存M条边，然后再进行普通的遍历算法，效率显然不高。
再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：
第一行是N，M。
N为问题涉及的人的个数（1N20000）。
这些人的编号为1,2,3,…,N。
下面有M行（1M2000000），每行有三个数ki,ai,bi，,ai,bi表示两个元素，ki为0或1，ki为1时表示这是一条边的信息，即ai,bi是亲戚关系；ki为0时表示是一个提问，根据此行以前所得到的信息，判断ai,bi是否亲戚，对于每条提问回答Yes或者No。
这个问题比原问题更复杂些，需要在任何时候回答提问的两个人的关系，并且对于信息提示还要能立即合并两个连通块。
采用连通图思想显然在实现上就有所困难，因为要表示人与人之间的关系。
用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。
以后每次给出一个亲戚关系时，就将两个集合合并。
这样实时地得到了在当前状态下的集合关系。
如果有提问，即在当前得到的结果中看两元素是否属于同一集合。
对于样例数据的解释如下图1：
输入关系分离集合
初始状态{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}
（2,4）{1}{2,4}{3}{5}{6}{7}{8}{9}{10}
（5,7）{1}{2,4}{3}{5,7}{6}{8}{9}{10}
（1,3）{1,3}{2,4}{5,7}{6}{8}{9}{10}
（8,9）{1,3}{2,4}{5,7}{6}{8,9}{10}
（1,2）{1,2,3,4}{5,7}{6}{8,9}{10}
（5,6）{1,2,3,4}{5,6,7}{8,9}{10}
（2,3）{1,2,3,4}{5,6,7}{8,9}{10}
图1
由图1可以看出，操作是在集合的基础上进行的，没有必要保存所有的边，而且每一步得到的划分方式是动态的。
那么，如何来实现以上的算法思想呢？
我们就用到并查集。
二、并查集的基本思想
1、什么叫并查集
并查集（union-findset）是一种用于分离集合操作的抽象数据类型。
它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对（a,b）时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。
“并”、“查”和“集”三字由此而来。
在这种数据类型中，n个不同的元素被分为若干组。
每组是一个集合，这种集合叫做分离集合（disjointset）。
并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。
例如，有这样的问题：
初始时n个元素分属不同的n个集合，通过不断的给出元素间的联系，要求实时的统计元素间的关系（是否存在直接或间接的联系）。
这时就有了并查集的用武之地了。
元素间是否有联系，只要判断两个元素是否属于同一个集合；而给出元素间的联系，建立这种联系，则只需合并两个元素各自所属的集合。
这些操作都是并查集所提供的。
并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。
数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。
并查集的数据结构实现方法很多，一般用的比较多的是，数组实现、链表实现和树实现。
2、并查集支持的操作
并查集的数据结构记录了一组分离的动态集合S={S1,S2,…,Sk}。
每个集合通过一个代表加以识别，代表即该元素中的某个元素，哪一个成员被选做代表是无所谓的，重要的是：
如果求某一动态集合的代表两次，且在两次请求间不修改集合，则两次得到的答案应该是相同的。
动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现需要支持如下操作：
MAKE-SET（x）：
建立一个新的集合，其仅有的成员（同时就是代表）是x。
由于各集合是分离的，要求x没有在其它集合中出现过。
UNION（x,y）：
将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。
结果的集合代表是Sx∪Sy的某个成员。
一般来说，在不同的实现中通常都以Sx或者Sy的代表作为新集合的代表。
此后，由新的集合S代替了原来的Sx和Sy。
FIND-SET（x）：
返回一个指向包含x的集合的代表。
三、并查集的实现及优化
1、并查集的数组实现
实现并查集的最简单的方法是用数组记录每个元素所属的集合的编号。
查找元素所属的集合时，只需读出数组中记录的该元素所属集合的编号即可，时间复杂度为O
（1）。
合并两元素各自所属的集合时，需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的编号值，时间复杂度为O（n）。
由于实现简单，所以实际使用的很多。
以上的数组实现虽然很方便，但是合并的代价太大。
在最坏情况下，所有集合合并成一个集合的总代价可以达到O（n2）。
2、并查集的链表实现
我们需要用一定的数据结构来组织动态的集合，同一集合中的所有元素应该是联系在一起的。
一种比较简单的想法是用链表来实现，每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类，另有一个指针指向它的下一个元素,同时为了方便实现，再设一个指针last表示链表中的最后一个元素（表尾）。
可以选择静态数组（一般来说这种问题处理的对象都是连续整数，可以用下标来对应元素）来实现，定义一个记录为
typenode=record
head,next,last:
integer;
end;
varS:
array[1..maxn]ofnode;
可以得到MAKE-SET和FIND-SET的实现为：
MAKE-SET（x）
{S[x].head=x;S[x].next=0;}
FIND-SET（x）
{returnS[x].head}
两个过程的时间复杂度都为O
（1）。
注意到我们采用链表以后，当有两个元素（x,y）,FIND-SET（x）≠FIND-SET（y）时，两者对应不同的集合，需要将两个链表合并，做法是将一个表的表头直接接到另一个表的表尾，这步操作很简单，但势必造成修改后需要把接上去的那个表的所有head值修改，这需要线性的赋值操作，其复杂度与选择接在尾部的链表长度成正比。
现在我们讨论UNION（x,y）的实现，假设UNION（x,y）的参数是有序的，即把y属于的集合合并到x的集合。
有两种实现方法：
（1）简单实现
不考虑任何因素，出现FIND-SET（x）≠FIND-SET（y）时，直接将y的表头接到x的尾，同时将y中所在集合元素所有元素的head设为FIND-SET（x）。
同时x的表尾也应该设为原y的表尾。
注意last指针其实只要在表头结点中记录即可，因为每一次查到FIND-SET（x）都可以得到表头元素。
而链表中其他元素重新记录last是无意义的。
考虑输入数据的特殊性，我们总是把y接到x里去，那么如果y所在的集合非常大，每次赋值的代价就会非常高，比如出现输入为：
（2，1），（3，1），（4，1），（5，1），（6，1）…（n,1）
显然y所在的集合越来越庞大，对于这种方法最坏情况下时间复杂度为O（n^2）。
（2）快速实现
上述简单实现非常不理想，针对y可能比较大的这个问题，可以很快产生一个聪明的想法：
不妨比较x和y所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但耗费肯定不比原来差。
这就是快速实现的思路。
可以在node里多设一个域number，用来记录此条链表中成员的个数。
显然number记录在表头元素中即可，将两表合并的时候，只要将表的number相加，因此维护起来是非常方便的。
这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的number。
可以证明这种方法的效率。
当有n个元素时，在UNION上的花费（即重新赋值的次数）的上界是O（nlogn）。
考虑一个固定的对象x，当x的代表指针（head）被更新时，x必是属于一个较小的集合，因此，x的代表指针第一次更新后，结果集合必然至少有2个元素，类似的，下一次更新后，x所在的集合至少有4个元素。
继续下去，可以发现，x的代表指针最多被更新logn次，因为当x所在集合元素已经等于n以后，不可能再发生UNION操作。
所以，总共有n个元素时，操作的总次数不超过nlogn次。
这就保证了整个算法的复杂度是理想的。
合并两个集合时的实现过程如下：
UNION（x,y）
{x=FIND-SET（x）;
y=FIND-SET（y）;
ifx.number>y.numberthenUNION（x,y）
elseUNION（y,x）;
}
并查集的链表实现是一种非常容易接受的算法，并且它的效率也是令人满意的。
其实它的思路和数组完全一样，所以实际使用较少。
3、并查集的树实现
实现并查集的另一种方法是利用树。
我们用有根树来表示集合，树中的每个节点包含集合的一个成员，每棵树表示一个集合。
多个集合形成森林态，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点都用一个父指针表示它的附属关系。
注意：
在同一棵树中的结点属于同一个集合，虽然它们在树中存在父子结点关系，但并不意味着它们之间存在从属关系。
树的指针起的只是联系集合中元素的作用。
在并查集中，每个分离集合对应的一棵树，称为分离集合树。
整个并查集也就是一棵分离集合森林。
如图2表示了这种关系，其包含两个集合{b,c,e,h},{d,f,g}分别以c和f作为代表。
图2
这种树结构，也可以简单地用静态数组实现，设p[x]表示x元素所指向的父亲。
MAKE-SET（x）：
p[x]=x;
FIND-SET（x）：
要从x开始，向上寻找它的父亲，直到找到根为止。
UNION（x,y）：
只要使一棵树的根指向另一棵树的根，即成为一棵子树。
可以发现，元素之间的联系是靠指针来实现的，与链表的实现相比，所需要进行的修改少了许多。
但可以发现，UNION（x,y）虽然是简便了许多，但是FIND-SET（x）则需要从x开始，经过一条可能比较长的路径，才能找到树根。
具体实现如下：
（1）查找一个元素所属的集合
在分离集合森林中，每一棵分离集合树对应一个集合。
要查找某一元素所属的集合，就是要找这个元素对应的结点所在的分离集合树。
不妨以分离集合树的根结点的编号来表示这个分离集合树。
这样，查找一个结点所在的分离集合树，也就是查找该结点所在分离集合树的根结点了。
查找树的根结点的方法很简单，只需任取树中一结点（不妨就取我们要查找的那个结点），沿父结点方向一直往树根走：
初始时，取一个结点，走到它的父结点，然后以父结点为基点，走到父结点的父结点……直至走到一个没有父结点的结点为止，这个结点就是树的根结点。
如图3，描述了查找一个结点的过程（黑色结点为当前查找结点）。
图3
查找算法的复杂度取决于查找结点的深度，假设查找结点的深度为h，则算法的时间复杂度为O（h）。
（2）两个元素各自所属的集合的合并
在分离集合森林中，分离集合是用分离集合树来表示的。
要合并两个元素各自所属的集合，也就是合并两元素所对应的两个结点各自所在的分离集合树。
现在的问题就是如何合并两棵分离集合树。
考虑到在分离集合森林中，只要结点属于同一棵树，即被视为在同一个集合中，而不管具体是如何相连的。
那么，我们只需简单的将一棵分离集合树作为另一棵的子树，即可使两棵树合并为一棵。
如图4，描述的是将两棵分离集合树D1和D2合并的过程（D1作为D2的根结点的一棵子树）。
图4
要完成上述合并，首先要找到两棵分离集合树的根结点，这可以通过调用两次查找算法得到。
得到根结点后，只需改变其中一个根结点，令它的父结点为另一个根结点即可，代价为O
（1）。
因此，整个合并算法的复杂度主要在查找根结点部分，为O（h）。
（3）优化查找与合并算法
前面提到，分离集合森林的查找与合并的时间复杂度都是O（h）。
也就是说，查找与合并的时间复杂度主要取决于树的深度。
就平均情况而言，树的深度应该在logn的数量级，n为结点个数，所以分离集合森林查找与合并的平均时间复杂度为O（logn）。
但是，在最坏情况下，一棵树的深度可能达到n，如图5。
这时的查找与合并的时间复杂度都达到了O（n）。
这是我们不愿意看到的，因此必须想方设法避免出现这种情况。
为了提高效率，可以考虑在UNION（x,y）和FIND-SET（x）上作一些文章。
图5
①优化合并过程
分析一下前面那棵深度为n的分离集合树的形成过程，可以看出，这是合并不当的后果。
当合并图6的两棵分离集合树（A，B）时，显然将B树作为A树根结点的子树得到的树比较平衡，如图6中的C树（D树为A树作为B树根结点的子树得到的树）。
图6
一棵较平衡的树拥有比较低的深度，查找和合并的复杂度也就相应得较低。
因此，如果两棵分离集合树A和B，深度分别为hA和hB，则若hA>hB，应将B树作为A树的子树；否则，将A树作为B树的子树。
总之，总是深度较小的分离集合树作为子树。
得到的新的分离集合树C的深度hC，以B树作A树的子树为例，hC=max{hA,hB+1}。
这样合并得到的分离集合树，其深度不会超过logn，是一个比较平衡的树。
因此，查找与合并的时间复杂度也就稳定在O（logn）了。
②优化查找过程
对于查找过程有两个方面的启发式方法都很有效，分别是按秩合并和路径压缩优化。
A．按秩合并
可以联系一下链表的优化，我们是选择比较小的一个集合归并到大的集合里去。
对于有根树的结构，很类似地，也可以记录树上的节点数，将较小的树的根指向较大的树。
但是有根树的结构又有非常特殊的地方，它的一个节点下面可能挂有很多子树；从前面分析也可以看出，主要的时间花在了FIND-SET（x）上，只要使得树中不存在一条偏长的路径，即使得各条路径的长度都比较平均了，那么算法就不会出现特别退化的情况。
对每个结点，用一个秩（rank）来近似子树大小对数，同时它也是该节点高度的一个上界。
进行UNION的时候，只要让具有较小秩的根指向具有较大秩的根。
如果两根的秩相等，只要使其中一个根指向另一个，同时秩应当增加1。
这十分类似于统计节点个数，但这里统计的是树的深度。
B．路径压缩优化方法
在分离集合森林中，分离集合是用分离集合树来表示的。
分离集合树是用来联系集合中的元素的，只要同一集合中的元素在同一棵树上，不管它们在树中是如何被联系的，都满足分离集合树的要求。
如图7，这两棵分离集合树是等价的，因为它们所包含的元素相同。
显然，右边那棵树比较“优秀”，因为它具有比较低的深度，相应的，查找与合并的时间复杂度也较低。
那么，我们就应该使分离集合树尽量向右树的形式靠拢。
图7
在查找一个结点所在树的根结点的过程中，要经过一条从待查结点到根结点的路径。
我们不妨就让这些路径上的结点直接指向根结点，作为根结点的子结点。
这样，这些路径上的结点仍在分离集合中，整棵树仍然满足分离集合树的要求，而路径上的结点的深度无疑降低了，这些点及其子树上的结点的查找复杂度大大降低。
如图8，描述了在一棵分离集合树查找结点7的前后所呈现出的结构。
图8
这种改变结点所指方向以降低结点深度，从而缩短查找路径长度的方法，叫做路径压缩。
实现路径压缩的最简单的方法是在查找从待查结点到根结点的路径时走两遍，第一遍找到树的根结点，第二遍改变路径上结点指向根结点（使它们的父结点为根结点）。
使用路径压缩大大提高了查找算法的效率。
如果将带路径压缩的查找算法与优化过的合并算法联合使用，则可以证明，n次查找最多需要用O（n·α（n））时间。
α（n）是单变量阿克曼函数的逆函数，它是一个增长速度比logn慢的多但又不是常数的函数，在一般情况下α（n）≤4，可以当作常数看。
这种方法是在FIND-SET（x）过程中作一些改进。
设想，从x到它的根，我们必须经过一条路径，显然这条路径上的所有的根与x的根是同一个根，那么不妨在得到结果的同时，顺便把这条路上全部节点的根都改成x的根，也就是说，对这些节点进行了分散，其结果是，下一次如果再有这条路上的点进行FIND-SET（x）时，只要经过一步就可以找到根。
可以认为是x顺便帮了帮大家的忙，把好处带给了大家，因此其它节点以后都省事了。
图9
如图9，FIND-SET（x）后变为了图10的结构：
图10
使用这两种方法优化后的代码：
MAKE-SET（x）
{p[x]=x；rank[x]=0；}
UNION（x,y）
{x=FIND-SET（x）；y=FIND-SET（Y）；
ifrank[x]>rank[y]thenp[y]=x
else{p[x]=y
ifrank[x]=rank[y]
thenrank[y]=rank[y]+1;
}
}
FIND-SET（x）
{ifx<>p[x]thenp[x]=FIND-SET（p[x]）；
returnp[x]；
}
可以看到FIND-SET（x）是一个递归的过程。
它的实现非常简洁，同时我们的方法也可以保证递归深度不会很深。
事实上只要使用这两种方法中的任何一种，算法的效率都会大大提高。
当两种方法结合起来以后，效率更高，几乎可以接近n的线性复杂度。
对于其效率的证明，是十分有意思的，但需要比较复杂的讨论。
对于应用来说，只要能够记住这两种实现方法。
四、引例的实现程序和部分测试数据
1、数组实现（relation1.pas）
Programrelation1;
const
inf='relation.in';
ouf='relation.out';
maxn=20000;
type
eletype=record
rank,father:
integer;
end;
procedureinit;
begin
assign（input,inf）;
reset（input）;
assign（output,ouf）;
rewrite（output）;
end;
procedureendit;
begin
close（input）;
close（output）;
end;
procedurework;
var
opt:
array[1..maxn]ofeletype;
m,i,q:
longint;
n,x,y:
integer;
proceduremdf（r1,r2:
integer）;
var
path:
array[1..maxn]ofinteger;
k,i:
integer;
begin
k:
=0;
repeat
inc（k）;
path[k]:
=r1;
r1:
=opt[r1].father;
untilr1=opt[r1].father;{查r1所属集合的代表}
fori:
=1tok-2doopt[path[i]].father:
=r1;{路径压缩优化，把这个路径上的点全部指向根结点}
k:
=0;
repeat
inc（k）;
path[k]:
=r2;
r2:
=opt[r2].father;
untilr2=opt[r2].father;
fori:
=1tok-2doopt[path[i]].father:
=r2;{同上}
ifr1=r2thenexit;{r1和r2已属于同一集合，则退出；否则做下面的合并}
ifopt[r1].rankthenbegin
opt[r1].father:
=r2;
inc（opt[r2].rank,opt[r1].rank）;
end
elsebegin
opt[r2].father:
=r1;
inc（opt[r1].rank,opt[r2].rank）;
end;
end;
begin{work}
readln（n,m）;
fori:
=1tondobegin{初始化}
opt[i].father:
=i;
opt[i].rank:
=1;
end;
fori:
=1tomdobegin
readln（x,y）;
mdf（x,y）;{建立关联}
end;
readln（q）;
fori:
=1toqdo
begin
readln（x,y）;
repeat
x:
=opt[x].father;
untilx=opt[x].father;{查x所属集合的代表}
repeat
y:
=opt[y].father;
untily=opt[y].father;{查y所属集合的代表}
ifopt[x].father=opt[y].father
thenwriteln（'Yes'）
elsewriteln（'No'）;
end;
end;
Begin{main}
init;
work;
endit
end.
2、链表实现（relation2.pas）
Programrelation2;
constmaxn=20000;
typerec=record
next,head,
升级会员 