信息學(xué)并查集

1、并查集并查集的定義如果給出各個(gè)元素之間的聯(lián)系，要求將這些元素分成幾個(gè)集合，每個(gè)集合中的元素直接或間接有聯(lián)系。在這類問題中主要涉及的是對(duì)集合的合并和查找，因此將這種集合稱為并查集。并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，常常在使用中以森林來表示。并查集的主要操作一開始，我們假設(shè)元素都是分別屬于一個(gè)獨(dú)立的集合里的。合并兩個(gè)不相交集合操作很簡(jiǎn)單：先設(shè)置一個(gè)數(shù)組Fatherx，表示x的“父親”的編號(hào)。 那么，合并兩個(gè)不相交集合的方法就是，找到其中一個(gè)集合最父親的父親（也就是最久遠(yuǎn)的祖先），將另外一個(gè)集合的最久遠(yuǎn)的祖先的父親指向它。Pascal代碼：function judge(x,y:integer):boole

2、an;其中GetFather是下面將講到的操作 var fx,fy:integer; begin fx:=getfather(x); fy:=getfather(y); If fx=fy then exit(true) else judge:= false; fatherfx := fy;指向最祖先的祖先 end;判斷兩個(gè)元素是否屬于同一集合仍然使用上面的數(shù)組。則本操作即可轉(zhuǎn)換為尋找兩個(gè)元素的最久遠(yuǎn)祖先是否相同。可以采用遞歸實(shí)現(xiàn)。Pascal代碼：Function Same(x,y:integer):boolean;begin if GetFather(x)=GetFather(y) then

3、 exit(true) else exit(false);end;并查集的優(yōu)化路徑壓縮剛才我們說過，尋找祖先時(shí)采用遞歸，但是一旦元素一多起來，或退化成一條鏈，每次GetFather都將會(huì)使用O(n)的復(fù)雜度，這顯然不是我們想要的。對(duì)此，我們必須要進(jìn)行路徑壓縮，即我們找到最久遠(yuǎn)的祖先時(shí)“順便”把它的子孫直接連接到它上面。這就是路徑壓縮了。使用路徑壓縮的代碼如下，時(shí)間復(fù)雜度基本可以認(rèn)為是常數(shù)的。Function getfather(v:integer):integer; begin if (fatherv=0) then getfather:=v else begin fatherv:=getfa

4、ther(fatherv);路徑壓縮 getfather:=fatherv; end; end;Procedure Initialize;var i:integer;begin for i:=1 to maxv do Fatheri:=i;end; Function GetFather(v:integer):integer;begin if Fatherv=v then exit(v) else Fatherv:=GetFather(v); exit(Fatherv);end;并查集的啟發(fā)式合并為了把兩個(gè)集合S1和S2并起來，只需要把S1的根的父親設(shè)置為S2的根（或把S2的根的父親設(shè)置為S1的

5、根）就可以了。這里有一個(gè)優(yōu)化：讓深度較小的樹成為深度較大的樹的子樹，這樣查找的次數(shù)就會(huì)少些。這個(gè)優(yōu)化稱為啟發(fā)式合并?？梢宰C明：這樣做以后樹的深度為O(logn)。即：在一個(gè)有n個(gè)元素的集合，我們將保證移動(dòng)不超過logn次就可以找到目標(biāo)。function judge(x,y:integer):boolean; var fx,fy : integer; begin fx := getfaher(x); fy := gefather(y); If fx=fy then exit(true) else judge := false; if rankfxrankfy then fatherfy := f

6、x else begin fatherfx := fy; if rankfx=rankfy then inc(rankfy); end; end;初始化：fillchar(rank,sizeof(rank),0);并查集的時(shí)間復(fù)雜度并查集進(jìn)行n次查找的時(shí)間復(fù)雜度是O(n)（執(zhí)行n-1次合并和mn次查找）。其中是一個(gè)增長(zhǎng)極其緩慢的函數(shù)，它是阿克曼函數(shù)（Ackermann Function）的某個(gè)反函數(shù)。它可以看作是小于5的。所以可以認(rèn)為并查集的時(shí)間復(fù)雜度幾乎是線性的。并查集的實(shí)際應(yīng)用1、親戚 問題描述： 若某個(gè)家族人員過于龐大，要判斷兩個(gè)是否是親戚，確實(shí)還很不容易，現(xiàn)在給出某個(gè)親戚關(guān)系圖，求任意

7、給出的兩個(gè)人是否具有親戚關(guān)系。規(guī)定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。 輸入文件： 第一行：三個(gè)整數(shù)n,m,p，（n=5000,m=5000,p=5000），分別表示有n個(gè)人，m個(gè)親戚關(guān)系，詢問p對(duì)親戚關(guān)系。以下m行：每行兩個(gè)數(shù)Mi，Mj，1=Mi，Mj=N，表示Ai和Bi具有親戚關(guān)系。 接下來p行：每行兩個(gè)數(shù)Pi，Pj，詢問Pi和Pj是否具有親戚關(guān)系。 輸出文件： P行，每行一個(gè)Yes或No。表示第i個(gè)詢問的答案為“具有”或“不具有”親戚關(guān)系。源程序：type longint:=integer； const m

8、axn:=5000； var i,j,n,m,p,is,js:longint； father:array1.maxnof longint；function getfather(v:longint):longint;尋找根結(jié)點(diǎn)編號(hào)并壓縮路徑 begin if fatherv:=v then begin getfather=v；exit；end； fatherv:=getfather(fatherv)； getfather:=fatherv; end;procedure merge(x,y：longint)；合并兩個(gè)集合begin x:=getfather(x); y:=getfather(y);

9、 fatherx:=y; end;function judge(x,y:longint):Boolean； 判斷元素是否屬于同一結(jié)合begin x:=getfather(x)； y:=getfather(y)； if x=y then judge:=true else judge:=false；end；begin read(n,m,p)；for i:=1 to n do fatheri:=i；因?yàn)槊總€(gè)元素屬于單獨(dú)的一個(gè)集合，所以每個(gè)元素以自己作為根結(jié)點(diǎn) for i:=1 to m do begin read(is,js)； merge(is,js)；end；for i:=1 to p do b

10、egin read(is,js)； if judge(is,js) then writeln(Yes) else writeln(No)；end；end.這個(gè)問題已經(jīng)完全闡述了并查集的基本操作和作用。2、銀河英雄傳說 問題描述：公元五八一年，地球居民遷移至金牛座第二行星，在那里發(fā)表銀河聯(lián)邦創(chuàng)立宣言，同年改元為宇宙歷元年，并開始向銀河系深處拓展。 宇宙歷七九九年，銀河系的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭(zhēng)。泰山壓頂集團(tuán)派宇宙艦隊(duì)司令萊因哈特率領(lǐng)十萬余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊威利組織麾下三萬艘戰(zhàn)艦迎敵。 楊威利擅長(zhǎng)排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多，難免滋生驕氣。在這次決戰(zhàn)中，他將巴米

11、利恩星域戰(zhàn)場(chǎng)劃分成30000列，每列依次編號(hào)為1， 2， ， 30000。之后，他把自己的戰(zhàn)艦也依次編號(hào)為1， 2， ， 30000，讓第i號(hào)戰(zhàn)艦處于第i列(i = 1， 2， ， 30000)，形成“一字長(zhǎng)蛇陣”，誘敵深入。這是初始陣形。當(dāng)進(jìn)犯之?dāng)车竭_(dá)時(shí)，楊威利會(huì)多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，實(shí)施密集攻擊。合并指令為Mij，含義為讓第i號(hào)戰(zhàn)艦所在的整個(gè)戰(zhàn)艦隊(duì)列，作為一個(gè)整體（頭在前尾在后）接至第j號(hào)戰(zhàn)艦所在的戰(zhàn)艦隊(duì)列的尾部。顯然戰(zhàn)艦隊(duì)列是由處于同一列的一個(gè)或多個(gè)戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會(huì)使隊(duì)列增大。然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動(dòng)。在交戰(zhàn)中，他可以通過龐大

12、的情報(bào)網(wǎng)絡(luò)隨時(shí)監(jiān)聽楊威利的艦隊(duì)調(diào)動(dòng)指令。 在楊威利發(fā)布指令調(diào)動(dòng)艦隊(duì)的同時(shí)，萊因哈特為了及時(shí)了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會(huì)發(fā)出一些詢問指令：Cij。該指令意思是，詢問電腦，楊威利的第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。作為一個(gè)資深的高級(jí)程序設(shè)計(jì)員，你被要求編寫程序分析楊威利的指令，以及回答萊因哈特的詢問。 最終的決戰(zhàn)已經(jīng)展開，銀河的歷史又翻過了一頁輸入文件： 輸入文件galaxy.in的第一行有一個(gè)整數(shù)T（1T500，000），表示總共有T條指令。 以下有T行，每行有一條指令。指令有兩種格式： 1. Mij：i和j是兩個(gè)整數(shù)（1i ，j3000

13、0），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特竊聽到的楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，并且保證第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦不在同一列。 2.Cij：i和j是兩個(gè)整數(shù)（1i ，j30000），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特發(fā)布的詢問指令。 輸出文件： 輸出文件為galaxy.out。你的程序應(yīng)當(dāng)依次對(duì)輸入的每一條指令進(jìn)行分析和處理。如果是楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，則表示艦隊(duì)排列發(fā)生了變化，你的程序要注意到這一點(diǎn)，但是不要輸出任何信息； 如果是萊因哈特發(fā)布的詢問指令，你的程序要輸出一行，僅包含一個(gè)整數(shù)，表示在同一列上，第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦之間布置的戰(zhàn)艦數(shù)目。如果第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前不在同一列

14、上，則輸出-1。 分析：觀察這個(gè)題目，開始時(shí)每條戰(zhàn)艦作為獨(dú)立的隊(duì)列。隨著M命令的發(fā)布，分離的隊(duì)列不斷合并。而且途中我們需要知道一些元素（戰(zhàn)艦）的信息。這些性質(zhì)啟發(fā)我們應(yīng)用并查集的數(shù)據(jù)結(jié)構(gòu)解決。由于我們要得到的信息除了某條戰(zhàn)艦在哪個(gè)隊(duì)列，還要知道它在該隊(duì)列中的位置，因此需要對(duì)并查集進(jìn)行擴(kuò)充。基本框架：var Father，Count，Behind：array1.maxn of integer； 在同一隊(duì)列中的戰(zhàn)艦組成一個(gè)樹型結(jié)構(gòu)的并查集Fatherx 戰(zhàn)艦x的父指針。Fatherx=x，表明戰(zhàn)艦x為根節(jié)點(diǎn)。路徑壓縮后，樹中所有子節(jié)點(diǎn)的父指針指向根節(jié)點(diǎn)； Countx 以節(jié)點(diǎn)x為根的樹的節(jié)點(diǎn)數(shù)；

15、Behindx 戰(zhàn)艦x在列中的相對(duì)位置； 初始時(shí)，我們?yōu)槊恳凰覒?zhàn)艦建立一個(gè)集合，即 Fatherx=x Countx=1 Behindx=0（1x30000)1、查找根節(jié)點(diǎn)并進(jìn)行路徑壓縮 function Find_Father(x：integer)：integer；查找節(jié)點(diǎn)x所在樹的根節(jié)點(diǎn)，并進(jìn)行路徑壓縮 var i，j，f，next：integer； begin ix； 找出節(jié)點(diǎn)x所在樹的根節(jié)點(diǎn)f while Fatherii do iFatheri； fi；ix； while if do 按照自下而上的順序處理x的祖先節(jié)點(diǎn) begin nextFatheri；FatherIf；把節(jié)點(diǎn)i的

16、父節(jié)點(diǎn)設(shè)為f，完成路徑壓縮 jnext； repeat BehindiBehindi+Behindj；迭代求出路徑上每一個(gè)子節(jié)點(diǎn)相對(duì)于f的相對(duì)位置 jFatherj； until Fatherj=j； inext； end；while find_Fatherf； 返回x所在樹的根節(jié)點(diǎn) end； Find_Father 2、計(jì)算合并指令 procedure MoveShip(x，y：integer)；把x所在的集合合并入y所在的集合 var fx，fy：integer； begin fxfind_Father(x)；計(jì)算x所在樹的根節(jié)點(diǎn)fx fyfind_Father(y)；計(jì)算y所在樹的根節(jié)點(diǎn)

17、fy Fatherfxfy；將fx的父節(jié)點(diǎn)設(shè)為fy BehindfxCountfy；計(jì)算fx的相對(duì)位置為Countfy CountfyCountfy+Countfx；計(jì)算新集合的節(jié)點(diǎn)數(shù) end； MoveShip 3、計(jì)算詢問指令 procedure CheckShip(x，y：integer)；計(jì)算x節(jié)點(diǎn)和y節(jié)點(diǎn)的相對(duì)位置情況 var f1，f2：integer； begin f1Find_Father(x)；計(jì)算x所在樹的根f1 f2Find_Father(y)；計(jì)算y所在樹的根f2 if f1f2 若x，y不在一棵樹中，則返回-1，否則返回x和y間隔的戰(zhàn)艦數(shù) then writeln(-1) else writeln(abs(Behindx-Behindy)-1)； end； CheckShip 由此得出主程序： for i1 to maxn do 初始時(shí)為每一艘戰(zhàn)艦建立一個(gè)