并查集的定义.ppt

《并查集的定义.ppt》由会员分享，可在线阅读，更多相关《并查集的定义.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、并查集并查集的定义并查集的定义在一些应用问题中，我们需要划分n个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并。其间要反复用到查找一个元素在哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集。(给出各个元素之间的联系，要求将这些元素分成几个集合，每个集给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。的合并和查找

2、，因此将这种集合称为并查集。)并查集的数学模型是若干不相交的动态集合的集合SA,B,C,.，它支持以下的运算：(1)INITIAL(A,x)：构造一个取名为A的集合，它只包含一个元素x；(2)MERGE(A,B)：将集合A和B合并，其结果取名为A或B；(3)FIND(x)：找出元素x的所在集合，并返回该集合的名字。并查集的数学模型并查集的数学模型例如，对于S1,2,.,7，要求作出S的等价类划分满足给定的等价性条件:12，56，34，和14。我们首先将S的每一个元素看成一个等价类，然后顺序地处理所列的条件。每处理完一个条件，所得到的相应等价类列表如下:121,234567；561,2345,6

3、7；341,23,45,67；141,2,3,45,67。所得到的结果是1,2,3,45,67。用数组实现并查集用数组实现并查集Constmaxn=100;Vardata:array1.maxnofinteger;在一般情况下，data应定义为：array元素的子界类型of集合名的类型。合并：O(n)查找：O(1)将所有元素合并到一个集合：O(n2)建立一个集合建立一个集合 O(1)procedureinitial(A,x:integer);begindatax:=A;end;构造一个取名为构造一个取名为A的集合，它只包含一个元素的集合，它只包含一个元素x；查找一个元素所属集合查找一个元素所属

4、集合 O(1)functionfind(x:integer):integer;beginfind:=datax;end;找出元素找出元素x的所在集合，并返回该集合的名字。的所在集合，并返回该集合的名字。合并两个集合合并两个集合 O(n)proceduremerge(A,B:integer);vari:integer;beginfori:=1tondoifdatai=Bthendatai:=A;end;将集合将集合A和和B合并，其结果取名为合并，其结果取名为AConstmaxn=100;Vardata:array1.maxnofinteger;procedureinitial(A,x:integ

5、er);begindatax:=A;end;functionfind(x:integer):integer;beginfind:=datax;end;proceduremerge(A,B:integer);vari:integer;beginfori:=1tondoifdatai=Bthendatai:=A;end;用链表实现并查集用链表实现并查集合并：O(i)查找：O(1)将所有元素合并到一个集合：O(nlogn)从n个单元素集开始，至多执行n-1次的MERGE运算就可以将所有元素合并到一个集合中。用前面算法，执行n-1次MERGE运算需要O(n2)时间，效率太低。加速MERGE运算的一种方

6、法是将各个集合中的元素链接成一个表，使得当要把集合B合并到集合A上去的时候，只要遍历B的各个元素而不必遍历全部n个元素。但最坏情况下，合并所有元素的时间复杂度仍为O(n2)为了改善最坏情况下的复杂度，明显的策略是：每次合并时总是将小的集合合并到大的集合上去。datarecordsetheaders：array1.nofrecordcount：1.n；集合中元素的个数firstelement：1.n;第一个元素end；names：array1.nofrecordSetname：1.n；该元素所属集合nextelement：1.n该元素的下一个元素endend；例：集合1为1,3,4，集合2为2，

7、集合5为5,6。311200002500132014105650123456123456setheaders：names：procedureINITIAL(A:nametype;x:elementtype;varC:data);beginC.namesx.setname:=A;C.namesx.nextelement:=0;C.setheadersA.count:=1;C.setheadersA.firstelement.:=x;end;functionFIND(x:elementtype;varC:data):nametype;beginfind:=C.namesx.setname;end;

8、procedureMERGE(A,B:nametype;varC:data)；Vari:elementtype;BeginifC.setheadersA.countC.setheadersB.countthenbegin将B合并到Ai:=C.setheadersB.firstelement;whileC.namesi.nextelement0dobeginC.namesi.setname:=A;i:=C.namesi.nextelement;end;C.namei.setname:=A;C.namei.nextelement:=C.sethteaersA.firstelement;C.seth

9、eadersA.firstelement:=C.setheadersB.firstelement;C.setheadersA.count:=C.setheadersA.count+C.setheadersB.count;C.setheadersB.count:=0;C.setheaersB.firstelement:=0endelse将A合并到BEnd;用树实现并查集用树实现并查集每个集合用一棵树表示。集合的元素名分别存放在树的结点中。树的每一个结点还存放着一个指向其父结点的指针。此外，还需要两个映射。一个是集合中的元素到存放该元素的元素名的树结点的映射；另一个是集合的名字到表示该集合的树的树

10、根的映射。A1,2,3,4，B5,6和C71234567A1,2,3,4，B5,6和C7123456将B合并到A合并：O(1)查找：O(logn)将所有元素合并到一个集合：O(n)注：每次应将小树合并到大树中，注：每次应将小树合并到大树中，否则最坏情况下树会退化成一条否则最坏情况下树会退化成一条链，使查找的时间复杂度为链，使查找的时间复杂度为O(n)。data=array1.nofrecord下标为元素的子界类型setname:1.n;集合名称parent:1.n;count:1.n;以此节点为根的树层数end;用父亲数组实现并查集procedureINITIAL(A:nametype;x:e

11、lementtype;varC:data);beginCx.setname:=A;Cx.parent:=0;Cx.count:=1;end;functionFIND(x:elementtype;varC:data):nametype;BeginwhileCx.parent0dox:=Cx.parent;find:=Cx.setname;end;procedureMERGE(A,B:nametype;varC:data)；Vari:elementtype;Begin查找A的树根元素x,B的树根元素yifCx.countCy.countthenCy.parent:=A将B合并到AelseCA.pa

12、rent:=B;将A合并到BEnd;边边查查询边询边“路径压缩路径压缩”其其实实，我我们们还还能能将将集集合合查查找找的的算算法法复复杂杂度度进进一一步步降降低低：采采用用“路路径径压压缩缩”算算法法。它它的的想想法法很很简简单单：在在集集合合的的查查找找过过程程中中顺顺便便将将树树的的深深度度降降低低。采采用用路路径径压压缩缩后后，每每一一次次查查询询所所用用的的时时间间复复杂杂度度为为增增长长极极为为缓缓慢慢的的ackermanackerman函函数数的的反反函函数数（x x）。对对于于可可以以想想象象到的到的n n，（n n）都是在都是在5 5之内的。之内的。functionFIND(x

13、:elementtype;varC:data):nametype;Vary,tmp:nametype;Beginy:=x;whileCx.parent0dox:=Cx.parent;find:=Cx.setname;whileCy.parent0dobegintmp:=y;y:=Cy.parent;Ctmp.parent:=x;end;end;亲戚或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情

14、况下，最好的帮手是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如同Xuebin和Grant是亲戚，Grant和Tension是亲戚等，从这些信息中，你可以推出Xuebin和Tension是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。输入输出样例输入文件名：输入文件名：Relations.in10 72 45 71 38 91 25 62 333 47 108 9输出文件名：输出文件名：Relations.outYesNoYesprocedureinitial(A,x:integer);begindatax:=A;end;functionfind(x:inte

15、ger):integer;beginfind:=datax;end;proceduremerge(A,B:integer);vari:integer;beginfori:=1tondoifdatai=Bthendatai:=A;end;BEGINassign(f,relations.in);reset(f);readln(f,n,m);fori:=1tondoinitial(i,i);fori:=1tomdobeginreadln(f,ai,bi);merge(ai,bi);end;readln(f,q);assign(fout,relations.out);rewrite(fout);for

16、i:=1toqdobeginreadln(f,ai,bi);iffind(ai)=find(bi)thenwriteln(fout,Yes)elsewriteln(fout,No);end;close(f);close(fout);END.破译密文破译密文信息的明文是由0和1组成的非空序列。但在网络通信中，为了信息的安全性，常对明文进行加密，用密文进行传输。密文是由0、1和若干个密码字母组成，每个密码字母代表不同的01串，例如，密文=011a0bf00a01。密码破译的关键是确定每个密码的含义。经过长期统计分析，现在知道了每个密码的固定长度，如今，我方又截获了敌方的两段密文S1和S2，并且知道

17、S1=S2，即两段密文代表相同的明文。你的任务是帮助情报人员对给定的两段密文进行分析，看一看有多少种可能的明文。输入输出样例输入输出样例输入文件：输入文件：t4.in100ad1cc14a2d3c4b50输出文件：输出文件：t4.out2样例分析100ad1cc14a2d3c4b50a1a2d1d2d3c1c2c3c4b1b2b49b50样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c4101a1a2c1c2c3c4d1d2d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c4101,c1a1a2c2c3c4d1d

18、2d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c410,c21,c1a1a2c3c4d1d2d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c410,c2,c31,c1a1a2c4d1d2d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c410,c2,c31,c1a1,c4a2d1d2d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c410,c2,c31,c1,a2a1,c4d1d2d3样例分析100ad1=100a1a2d

19、1d2d31cc1=c1c2c3c4c1c2c3c410,c2,c3,d11,c1,a2a1,c4d2d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c410,c2,c3,d1,d21,c1,a2a1,c4d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c410,c2,c3,d1,d21,c1,a2a1,c4,d3样例分析100ad1=100a1a2d1d2d31cc1=c1c2c3c4c1c2c3c410,c2,c3,d1,d21,c1,a2a1,c4,d3样例分析100ad1=100a1a2d1d2d31c

20、c1=c1c2c3c4c1c2c3c411,c1,a20,c2,c3,d1,d2a1,c4,d3只有1个不定等价类，因此结果为21=2用树表示集合用树表示集合用树表示集合为了得到两个集合的并，只须把其中一个根结点的亲体字段置成指向另一个根结点。要做到这一点不难，只要我们为每个集合名保持一个指示字，使其指向表示该集合的树根结点即可。此外，如果每个根结点中有一个指向集合名的指示字，那么为确定一个元素当前属于哪个集合可沿着亲体连接到达该元素所在树的根，再使用上述指示字，即可找到该集合名。用树表示集合S1，S2和S3的数据表示法便可采取如下形式：用树表示集合find(i)：找出含有元素i的集合union(i,j):把根节点为i,j(ij)的两个集合予以合并