《并查集的定义》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,2345

3、67； 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:array

5、1.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

7、record Setname：1.n；该元素所属集合 nextelement：1.n该元素的下一个元素 end end；例：集合1为1,3,4，集合2为2，集合5为5,6。311200002500132014105650123456123456setheaders：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.firstelemen

8、t.:=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.setnam

9、e:=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合并到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)。dat

11、a=array1.n 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:

12、=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;边查询边边查询边“途径紧缩途径紧缩 其实，我们还能将集合查找的算法复杂度进一步降低：采用其实，我们还能将集合查找的算法复杂度进一步降低：采用“途径紧缩算法。它的想法很简单：在集合的查找过程中顺便途径紧缩算法。它的想法很简单：在集合的查找过程中顺便将树

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 beg

14、in tmp:=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 the

16、n 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

17、 writeln(fout,No); end; close(f);close(fout);END.破译密文破译密文 w信息的明文是由0和1组成的非空序列。但在网络通讯中，为了信息的平安性，常对明文进展加密，用密文进展传输。密文是由0、1和假设干个密码字母组成，每个密码字母代表不同的01串，例如，密文=011a0bf00a01。密码破译的关键是确定每个密码的含义。w 经过长期统计分析，如今知道了每个密码的固定长度，如今，我方又截获了敌方的两段密文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 a2d1d2d31

19、cc1 =c1c2c3c4 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 c2c3c