《并查集的定义》PPT课件.ppt

并 查 集,并查集的定义,在一些应用问题中，我们需要划分n个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并。其间要反复用到查找一个元素在哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集。,(给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。),并查集的数学模型是若干不相交的动态集合的集合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； 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:array1maxn of integer;,在一般情况下，data应定义为： array元素的子界类型 of 集合名的类型。,合并：O(n) 查找：O(1),将所有元素合并到一个集合：O(n2),建立一个集合 O(1),procedure initial(A,x:integer); begin datax:=A; end;,构造一个取名为A的集合，它只包含一个元素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合并，其结果取名为A,Const maxn=100; Var data:array1maxn 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运算就可以将所有元素合并到一个集合中。用前面算法，执行n-1次MERGE运算需要O(n2)时间，效率太低。 加速MERGE运算的一种方法是将各个集合中的元素链接成一个表，使得当要把集合B合并到集合A上去的时候，只要遍历B的各个元素而不必遍历全部n个元素。但最坏情况下，合并所有元素的时间复杂度仍为O(n2) 为了改善最坏情况下的复杂度，明显的策略是：每次合并时总是将小的集合合并到大的集合上去。,datarecord setheaders： array1n of record count：1n；集合中元素的个数 firstelement：1n;第一个元素 end； names： array1n of record Setname：1n；该元素所属集合 nextelement：1n该元素的下一个元素 end end；,例：集合1为1,3,4，集合2为2，集合5为5,6。,1 2 3 4 5 6,1 2 3 4 5 6,setheaders：,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; end; 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:=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合并到B End;,用树实现并查集,每个集合用一棵树表示。集合的元素名分别存放在树的结点中。树的每一个结点还存放着一个指向其父结点的指针。此外，还需要两个映射。一个是集合中的元素到存放该元素的元素名的树结点的映射；另一个是集合的名字到表示该集合的树的树根的映射。,A1,2,3,4，B5,6和C7,1,2,3,4,5,6,7,A1,2,3,4，B5,6和C7,1,2,3,4,5,6,将B合并到A,合并：O(1) 查找：O(logn) 将所有元素合并到一个集合：O(n),注：每次应将小树合并到大树中，否则最坏情况下树会退化成一条链，使查找的时间复杂度为O(n)。,data=array1n of record 下标为元素的子界类型 setname:1n;集合名称 parent:1n; count:1n;以此节点为根的树层数 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.setname; 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;,边查询边“路径压缩”,其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数（x）。对于可以想象到的n，（n）都是在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:=y;y:=Cy.parent; Ctmp.parent:=x; end; end;,亲戚 或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手是计算机。 为了将问题简化，你将得到一些亲戚关系的信息，如同Xuebin和Grant是亲戚，Grant和Tension是亲戚等，从这些信息中，你可以推出Xuebin和Tension是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。,输入输出样例,输入文件名：Relations.in 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9 输出文件名：Relations.out Yes No Yes,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;,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 writeln(fout,No); end; close(f);close(fout); END.,破译密文,信息的明文是由0和1组成的非空序列。但在网络通信中，为了信息的安全性，常对明文进行加密，用密文进行传输。密文是由0、1和若干个密码字母组成，每个密码字母代表不同的01串，例如，密文=011a0bf00a01。密码破译的关键是确定每个密码的含义。 经过长期统计分析，现在知道了每个密码的固定长度，如今，我方又截获了敌方的两段密文S1和S2，并且知道S1=S2，即两段密文代表相同的明文。你的任务是帮助情报人员对给定的两段密文进行分析，看一看有多少种可能的明文。,输入输出样例,输入文件：t4.in 100ad1 cc1 4 a 2 d 3 c 4 b 50 输出文件：t4.out 2,样例分析,100ad1 cc1 4 a 2 d 3 c 4 b 50,a1a2 d1d2d3 c1c2c3c4 b1b2b49b50,样例分析,100ad1=1 0 0 a1 a2d1d2d31 cc1 =c1c2c3c4 c1 c2c3c41,0 1 a1 a2 c1 c2 c3 c4,d1 d2 d3,样例分析,100ad1=1 0 0 a1 a2d1d2d31 cc1 =c1c2c3c4 c1 c2c3c41,0 1,c1 a1 a2 c2 c3 c4,d1 d2 d3,样例分析,100ad1=1 0 0 a1 a2d1d2d31 cc1 =c1c2c3c4 c1 c2c3c41,0,c2 1,c1 a1 a2 c3 c4,d1 d2 d3,样例分析,100ad1=1 0 0 a1 a2d1d2d31 cc1 =c1c2c3c4 c1 c2c3c41,0,c2,c3 1,c1 a1 a2 c4,d1 d2 d3,样例分析,100ad1=1 0 0 a1 a2d1d2d31 cc1 =c1c2c3c4 c1 c2c3c41,0,c2,c3 1,c1 a1,c4 a2,d1 d2 d3,样例分析,100ad1=1 0 0 a1 a2d1d2d31 cc1 =c1c2c3c4 c1 c2c3c41,0,c2,c3 1,c1,a2 a1,c4,d1 d2 d3,样例分析,100ad1=1 0 0 a1 a2d1d2d31 cc1 =c1c2c3c4 c1 c2c3c41,0,c2,c3,d1 1,c1,a2 a1,c4,d2 d3,样例分析,100ad1=1 0 0 a1