《并查集的定義》ppt課件

1、并 查 集并查集的定義并查集的定義 在一些運用問題中，我們需求劃分n個不同的元素成假設(shè)干組，每一組的元素構(gòu)成一個集合。這種問題的一個處理方法是，在開場時，讓每個元素自成一個單元素集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并。其間要反復(fù)用到查找一個元素在哪一個集合的運算。適宜于描畫這類問題的籠統(tǒng)數(shù)據(jù)類型稱為并查集。(給出各個元素之間的聯(lián)絡(luò)，要求將這些元素分成幾個集合，每個集給出各個元素之間的聯(lián)絡(luò)，要求將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)絡(luò)。在這類問題中主要涉及的是對集合合中的元素直接或間接有聯(lián)絡(luò)。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為并查集。的合

2、并和查找，因此將這種集合稱為并查集。) 并查集的數(shù)學模型是假設(shè)干不相交的動態(tài)集合的集合SA,B,C,.，它支持以下的運算： (1)INITIAL(A,x)：構(gòu)造一個取名為A的集合，它只包含一個元素x； (2)MERGE(A,B)：將集合A和B合并，其結(jié)果取名為A或B； (3)FIND(x)：找出元素x的所在集合，并前往該集合的名字。并查集的數(shù)學模型并查集的數(shù)學模型 例如，對于S1,2,.,7，要求作出S的等價類劃分滿足給定的等價性條件:12，56，34，和14。 我們首先將S的每一個元素看成一個等價類，然后順序地處置所列的條件。每處置完一個條件，所得到的相應(yīng)等價類列表如下: 12 1,2345

3、67； 56 1,2345,67； 34 1,23,45,67； 14 1,2,3,45,67。所得到的結(jié)果是1,2,3,45,67。用數(shù)組實現(xiàn)并查集用數(shù)組實現(xiàn)并查集Const maxn=100;Var data:array1.maxn of integer;在普通情況下，data應(yīng)定義為：array元素的子界類型 of 集合名的類型。合并：O(n)查找：O(1)將一切元素合并到一個集合：O(n2)建立一個集合建立一個集合 O(1)procedure initial(A,x:integer);begin datax:=A;end;構(gòu)造一個取名為構(gòu)造一個取名為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合并，其結(jié)果取名為合并，其結(jié)果取名為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;用鏈表實現(xiàn)并查集用鏈表實現(xiàn)并查集合并：O(i)查找：O(1)將一切元素合并到一個集合：O(nlogn) 從n個單元素集開場，至多執(zhí)行n-1次的MERGE運算就可以將

6、一切元素合并到一個集合中。用前面算法，執(zhí)行n-1次MERGE運算需求O(n2)時間，效率太低。 加速MERGE運算的一種方法是將各個集合中的元素鏈接成一個表，使得當要把集合B合并到集合A上去的時候，只需遍歷B的各個元素而不用遍歷全部n個元素。但最壞情況下，合并一切元素的時間復(fù)雜度仍為O(n2) 為了改善最壞情況下的復(fù)雜度，明顯的戰(zhàn)略是：每次合并時總是將小的集合合并到大的集合上去。 datarecord setheaders： array1.n of record count：1.n；集合中元素的個數(shù) 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;用樹實現(xiàn)并

10、查集用樹實現(xiàn)并查集 每個集合用一棵樹表示。集合的元素名分別存放在樹的結(jié)點中。樹的每一個結(jié)點還存放著一個指向其父結(jié)點的指針。此外，還需求兩個映射。一個是集合中的元素到存放該元素的元素名的樹結(jié)點的映射；另一個是集合的名字到表示該集合的樹的樹根的映射。A1,2,3,4，B5,6和C71234567A1,2,3,4，B5,6和C7123456將B合并到A合并：O(1)查找：O(logn)將一切元素合并到一個集合：O(n)注：每次應(yīng)將小樹合并到大樹中，注：每次應(yīng)將小樹合并到大樹中，否那么最壞情況下樹會退化成一否那么最壞情況下樹會退化成一條鏈，使查找的時間復(fù)雜度為條鏈，使查找的時間復(fù)雜度為O(n)。dat

11、a=array1.n of record 下標為元素的子界類型 setname:1.n;集合稱號 parent:1.n; count:1.n;以此節(jié)點為根的樹層數(shù) end; 用父親數(shù)組實現(xiàn)并查集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;邊查詢邊邊查詢邊“途徑緊縮途徑緊縮 其實，我們還能將集合查找的算法復(fù)雜度進一步降低：采用其實，我們還能將集合查找的算法復(fù)雜度進一步降低：采用“途徑緊縮算法。它的想法很簡單：在集合的查找過程中順便途徑緊縮算法。它的想法很簡單：在集合的查找過程中順便將樹

13、的深度降低。采用途徑緊縮后，每一次查詢所用的時間復(fù)將樹的深度降低。采用途徑緊縮后，每一次查詢所用的時間復(fù)雜度為增長極為緩慢的雜度為增長極為緩慢的ackermanackerman函數(shù)的反函數(shù)函數(shù)的反函數(shù)x x。對。對于可以想象到的于可以想象到的n n，n n都是在都是在5 5之內(nèi)的。之內(nèi)的。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;親戚 或許他并不知道，他的某個朋友是他的親戚。他能夠是他的曾祖父的外公的女婿的外甥女的表姐的孫子。假設(shè)能得到完好的家譜，判別兩個人能否是親戚應(yīng)該是可行的，但假設(shè)兩個人的最近公共祖先與他們相隔好幾代，使得家譜非常龐大，那么檢驗親戚關(guān)系實非人力所能及。在這種情況下，最好的幫手是計算機。 為了將問題簡化，他將得到一些親戚關(guān)系的信息，好像Xuebin和Grant是親戚，Grant和Tension是親戚等，從這些信息中，他可以推出Xuebin和Tension是親戚。請寫一個程序，對于我們的關(guān)于親戚關(guān)系的提問，

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組成的非空序列。但在網(wǎng)絡(luò)通訊中，為了信息的平安性，常對明文進展加密，用密文進展傳輸。密文是由0、1和假設(shè)干個密碼字母組成，每個密碼字母代表不同的01串，例如，密文=011a0bf00a01。密碼破譯的關(guān)鍵是確定每個密碼的含義。w 經(jīng)過長期統(tǒng)計分析，如今知道了每個密碼的固定長度，如今，我方又截獲了敵方的兩段密文S1和S2，并且知道S1=S2，即兩段密文代表一樣的明文。他的義務(wù)是協(xié)助情報人員對給定的兩段密文進展分析，看一看有多少種能夠的明文。輸入輸出樣例輸入輸出

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