并查集的定义ppt课件

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的每一个元素看成一个等价类，然后顺序地处理所列的条件。每处理完一个条件，所得到的相应等价类列表如下: 12 1,234567

3、； 56 1,2345,67； 34 1,23,45,67； 14 1,2,3,45,67。所得到的结果是1,2,3,45,67。用数组实现并查集用数组实现并查集Const maxn=100;Var data:array1.maxn of integer;在一般情况下，data应定义为：array元素的子界类型 of 集合名的类型。合并：O(n)查找：O(1)将所有元素合并到一个集合：O(n2)建立一个集合建立一个集合 O(1)procedure initial(A,x:integer);begin datax:=A;end;构造一个取名为构造一个取名为A的集合，它只包含一个元素的集合，它只包

4、含一个元素x；查找一个元素所属集合查找一个元素所属集合 O(1)function find(x:integer):integer;begin find:=datax;end;找出元素找出元素x的所在集合，并返回该集合的名字。的所在集合，并返回该集合的名字。合并两个集合合并两个集合 O(n)procedure merge(A,B:integer);var i:integer;begin for i:=1 to n do if datai=B then datai:=A;end;将集合将集合A和和B合并，其结果取名为合并，其结果取名为AConst maxn=100;Var data:array1.

5、maxn of integer;procedure initial(A,x:integer);begin datax:=A;end;function find(x:integer):integer;begin find:=datax;end;procedure merge(A,B:integer);var i:integer;begin for i:=1 to n do if datai=B then datai:=A;end;用链表实现并查集用链表实现并查集合并：O(i)查找：O(1)将所有元素合并到一个集合：O(nlogn) 从n个单元素集开始，至多执行n-1次的MERGE运算就可以将所有

6、元素合并到一个集合中。用前面算法，执行n-1次MERGE运算需要O(n2)时间，效率太低。 加速MERGE运算的一种方法是将各个集合中的元素链接成一个表，使得当要把集合B合并到集合A上去的时候，只要遍历B的各个元素而不必遍历全部n个元素。但最坏情况下，合并所有元素的时间复杂度仍为O(n2) 为了改善最坏情况下的复杂度，明显的策略是：每次合并时总是将小的集合合并到大的集合上去。 datarecord setheaders： array1.n of record count：1.n；集合中元素的个数 firstelement：1.n;第一个元素 end； names： array1.n of re

7、cord Setname：1.n；该元素所属集合 nextelement：1.n该元素的下一个元素 end end；例：集合1为1,3,4，集合2为2，集合5为5,6。311200002500121155123456123456setheaders：names：procedure INITIAL (A:nametype;x:elementtype;var C:data);begin C. namesx.setname:=A; C. namesx.nextelement:=0; C. setheadersA.count:=1; C. setheadersA.firstelement.:=x;en

8、d;function FIND(x:elementtype;var C:data):nametype;begin find:=C.namesx.setname;end;procedure MERGE (A,B:nametype;var C:data)；Var i:elementtype;Begin if C.setheadersA.countC.setheadersB.count then begin将B合并到A i:=C.setheadersB.firstelement; while C.namesi.nextelement0 do begin C.namesi.setname:=A; i:

9、=C.namesi.nextelement; end; C.namei.setname:=A; C.namei.nextelement:=C.sethteaersA.firstelement; C.setheadersA.firstelement:=C.setheadersB.firstelement; C.setheadersA.count:=C.setheadersA.count+C.setheadersB.count; C.setheadersB.count:=0; C.setheaersB.firstelement:=0 end else 将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.n

11、 of record 下标为元素的子界类型 setname:1.n;集合名称 parent:1.n; count:1.n;以此节点为根的树层数 end; 用父亲数组实现并查集procedure INITIAL (A:nametype;x:elementtype;var C:data);begin Cx.setname:=A; Cx. parent:=0; Cx. count:=1;end;function FIND(x:elementtype;var C:data):nametype;Begin while Cx.parent0 do x:=Cx.parent; find:=Cx.setnam

12、e;end;procedure MERGE (A,B:nametype;var C:data)；Var i:elementtype;Begin 查找A的树根元素x,B的树根元素y if Cx.countCy.count then Cy.parent:=A 将B合并到A else CA.parent:=B; 将A合并到B End;边查询边边查询边“路径压缩路径压缩” 其实，我们还能将集合查找的算法复杂度进一步降低：采用其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩路径压缩算法。它的想法很简单：在集合的查找过程中顺算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径

13、压缩后，每一次查询所用的时间便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的复杂度为增长极为缓慢的ackermanackerman函数的反函数函数的反函数x x）。）。对于可以想象到的对于可以想象到的n n，n n都是在都是在5 5之内的。之内的。function FIND(x:elementtype;var C:data):nametype;Var y,tmp:nametype;Begin y:=x; while Cx.parent0 do x:=Cx.parent; find:=Cx.setname; while Cy.parent0 do begin tmp:

14、=y;y:=Cy.parent; Ctmp.parent:=x; end;end;亲戚 或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手是计算机。 为了将问题简化，你将得到一些亲戚关系的信息，如同Xuebin和Grant是亲戚，Grant和Tension是亲戚等，从这些信息中，你可以推出Xuebin和Tension是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给

15、出答案。 输入输出样例w输入文件名：输入文件名：Relations.inw10 72 45 71 38 91 25 62 333 47 108 9w输出文件名：输出文件名：Relations.outwYesNoYesprocedure initial(A,x:integer);begin datax:=A;end;function find(x:integer):integer;begin find:=datax;end;procedure merge(A,B:integer);var i:integer;begin for i:=1 to n do if datai=B then datai

16、:=A;end;BEGIN assign(f,relations.in);reset(f);readln(f,n,m); for i:=1 to n do initial(i,i); for i:=1 to m do begin readln(f,ai,bi); merge(ai,bi); end; readln(f,q);assign(fout,relations.out);rewrite(fout); for i:=1 to q do begin readln(f,ai,bi); if find(ai)=find(bi) then writeln(fout,Yes) else writel

17、n(fout,No); end; close(f);close(fout);END.破译密文破译密文 信息的明文是由0和1组成的非空序列。但在网络通信中，为了信息的安全性，常对明文进行加密，用密文进行传输。密文是由0、1和若干个密码字母组成，每个密码字母代表不同的01串，例如，密文=011a0bf00a01。密码破译的关键是确定每个密码的含义。 经过长期统计分析，现在知道了每个密码的固定长度，如今，我方又截获了敌方的两段密文S1和S2，并且知道S1=S2，即两段密文代表相同的明文。你的任务是帮助情报人员对给定的两段密文进行分析，看一看有多少种可能的明文。输入输出样例输入输出样例 输入文件：输入

18、文件：t4.in100ad1cc14a 2 d 3 c 4 b 50输出文件：输出文件：t4.out2 样例分析100ad1cc14a 2 d 3 c 4 b 50a1a2d1d2d3 c1c2c3c4 b1b2b49b50样例分析100ad1=1 0 0 a1 a2d1d2d31cc1 =c1c2c3c4 c1 c2c3c41 01a1a2c1c2c3c4d1d2d3样例分析100ad1=1 0 0 a1 a2d1d2d31cc1 =c1c2c3c4 c1 c2c3c41 01,c1a1a2c2c3c4d1d2d3样例分析100ad1=1 0 0 a1 a2d1d2d31cc1 =c1c2c

19、3c4 c1 c2c3c41 0,c21,c1a1a2c3c4d1d2d3样例分析100ad1=1 0 0 a1 a2d1d2d31cc1 =c1c2c3c4 c1 c2c3c41 0,c2,c31,c1a1a2c4d1d2d3样例分析100ad1=1 0 0 a1 a2d1d2d31cc1 =c1c2c3c4 c1 c2c3c41 0,c2,c31,c1a1,c4a2d1d2d3样例分析100ad1=1 0 0 a1 a2d1d2d31cc1 =c1c2c3c4 c1 c2c3c41 0,c2,c31,c1,a2a1,c4d1d2d3样例分析100ad1=1 0 0 a1 a2d1d2d31cc1 =c1c2c3c4 c1 c2c3c4