并查集(最終版).ppt

1、并查集,JSOI2015冬令營,并查集基本概念 并查集基本操作 并查集應(yīng)用舉例,問題描述：或許你并不知道，你的某個朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子！ 如果能得到完整的家譜，判斷兩個人是否親戚應(yīng)該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗親戚關(guān)系實非人力所能及。在這種情況下，最好的幫手就是計算機(jī)。為了將問題簡化，你將得到一些親戚關(guān)系的信息，如Marry和Tom是親戚，Tom和Ben是親戚，等等。從這些信息中，你可以推出Marry和Ben是親戚。,例1：親戚,輸入: 由兩部分組成： 第一部分以N，M開始。N為問題涉及的人的個數(shù)

2、。這些人的編號為1,2,3, N。下面有M行，每行有兩個數(shù)ai, bi，表示已知ai和bi是親戚。 第二部分以Q開始。以下Q行有Q個詢問，每行為ci, di，表示詢問ci和di是否為親戚。 輸出：對于每個詢問ci, di，輸出一行：若ci和di為親戚，則輸出“Yes”，否則輸出“No”。,請寫一個程序，對于我們的關(guān)于親戚關(guān)系的提問，以最快的速度給出答案。,輸入樣例（relation.in）： 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9,輸出樣例（relation.out）： Yes No Yes,問題規(guī)模1： 1 N 255 1 M 1 00

3、0 000 1 Q 1 000 000,各抒己見,思路點拔,題意分析 算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計 時間、空間復(fù)雜度估計及實踐細(xì)節(jié)討論 優(yōu)化思路討論,輸入關(guān)系 分離集合 初始狀態(tài) 12345678910 (2,4) 12,435678910 (5,7) 12,435,768910 (1,3) 1,32,45,768910 (8,9) 1,32,45,768,910 (1,2) 1,2,3,45,768,910 (5,6) 1,2,3,45,6,78,910 (2,3) 1,2,3,45,6,78,910,實時判斷,集 合,定義及運(yùn)算：var s:set of 1.100; 集合與集合：交A*B、并A+B

4、、差A(yù)-B，結(jié)果還是集合； 關(guān)系運(yùn)算 相等=、不相等、包含于=，結(jié)果為boolean； 元素與集合：x in s，結(jié)果為boolean；,集合的優(yōu)缺點：容易理解，運(yùn)算簡單； 數(shù)據(jù)量小、調(diào)試不方便；,問題規(guī)模2： 1 N 20000 1 M 1 000 000 1 Q 1 000 000,并查集,并查集（union-find set）是一種用于分離集合操作的抽象數(shù)據(jù)類型。它所處理的是“集合”之間的關(guān)系，即動態(tài)地維護(hù)和處理集合元素之間復(fù)雜的關(guān)系，當(dāng)給出兩個元素的一個無序?qū)?a,b)時，需要快速“合并”a和b分別所在的集合，這其間需要反復(fù)“查找”某個元素所在的集合?！安ⅰ薄ⅰ安椤焙汀凹比钟纱硕鴣?/p>

5、。在這種數(shù)據(jù)類型中，n個不同的元素被分為若干組。每組是一個集合，這種集合叫做分離集合（disjoint set）。并查集支持查找一個元素所屬的集合以及兩個元素各自所屬的集合的合并。,如何用已有的數(shù)據(jù)類型或數(shù)據(jù)結(jié)構(gòu)去構(gòu)造？,并查集本身不具有結(jié)構(gòu)，必須借助一定的數(shù)據(jù)結(jié)構(gòu)以得到支持和實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的選擇是一個重要的環(huán)節(jié)，選擇不同的數(shù)據(jù)結(jié)構(gòu)可能會在查找和合并的操作效率上有很大的差別，但操作實現(xiàn)都比較簡單高效。并查集的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)方法很多，一般用的比較多的是，數(shù)組實現(xiàn)、鏈表實現(xiàn)和樹實現(xiàn)。,并查集,并查集的數(shù)據(jù)結(jié)構(gòu)記錄了一組分離的動態(tài)集合S，S=S1,S2,Sk，每個集合通過一個“代表”加以識別，代表即該

6、集合中的某個元素（成員），哪一個成員被選做代表是無所謂的，重要的是：如果求某一動態(tài)集合的代表兩次，且在兩次請求間不修改此集合，則兩次得到的答案應(yīng)該是相同的。,動態(tài)集合中的每一元素是由一個對象來表示的，設(shè)x表示一個對象，并查集的實現(xiàn)需要支持如下操作：,并查集的基本操作, MAKE-SET（x） 建立一個新的集合，其僅有的成員（同時就是代表）是x。由于各集合是分離的，所以要求x沒有在其它集合中出現(xiàn)過。 UNION（x,y） 將包含x和y的動態(tài)集合（例如Sx和Sy）合并為一個新的集合，假定在此操作前這兩個集合是分離的。結(jié)果的集合代表是SxSy的某個成員。一般來說，在不同的實現(xiàn)中通常都以Sx或者Sy的

7、代表作為新集合的代表。此后，由新的集合S代替了原來的Sx和Sy。 FIND-SET（x） 返回一個包含x的集合的代表。,并查集的數(shù)組實現(xiàn),輸入樣例： 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9,UNION（x,y）過程演示：,S,1 2 3 4 5 6 7 8 9 10,S,1 2 3 4 5 6 7 8 9 10,用數(shù)組si記錄元素i所屬集合的編號。 MAKE-SET（x）：初始化只要si：=i； FIND-SET（x）：查找元素所屬的集合時，只需讀出si，時間復(fù)雜度為O(1)。 UNION（x,y）：合并兩元素各自所屬的集合時，需要將數(shù)組

8、中屬于其中一個集合的元素所對應(yīng)的數(shù)組元素值全部改為另一個集合的編號值，時間復(fù)雜度為O(n)。 實現(xiàn)簡單，實際使用較多。但是合并的代價太大，在最壞情況下，所有集合合并成一個集合的總代價會達(dá)到O(n2)。,每個集合對應(yīng)一個鏈表，它有一個表頭，每一個元素有一個指針指向表頭，表明了它所屬的類，另有一個指針指向它的下一個元素,同時為了方便實現(xiàn)，再設(shè)一個指針last表示鏈表中的最后一個元素（表尾）。 當(dāng)然，由于處理的對象一般都是連續(xù)整數(shù)，所以，可以選擇靜態(tài)數(shù)組（通過下標(biāo)）來模擬實現(xiàn)，如： type node = record head,next,last:integer; end; var S : arr

9、ay1.maxn of node;,并查集的鏈表實現(xiàn),MAKE-SET(x)：Sx.head = x;Sx.next = 0; FIND-SET(x)：return Sx.head; 兩個過程的時間復(fù)雜度都為O(1)。 采用鏈表時，當(dāng)有兩個元素(x,y),若FIND-SET（x） FIND-SET（y），則兩者對應(yīng)不同的集合，需要將兩個鏈表合并，做法是將一個表的表頭直接接到另一個表的表尾，這一步操作看似很簡單，但勢必造成修改后需要把接上去的那個表的所有head值修改，這需要線性的賦值操作，其復(fù)雜度與選擇接在尾部的鏈表長度成正比。,UNION(x,y)： 假設(shè)UNION(x,y)的參數(shù)是有序的，

10、即把y屬于的集合合并到x的集合有兩種實現(xiàn)方法：,（1）簡單實現(xiàn) 不考慮任何因素，出現(xiàn)FIND-SET（x） FIND-SET（y）時，直接將y的表頭接到x的表尾，同時將y中所在集合元素的head值設(shè)為FIND-SET(x)。同時x的表尾也應(yīng)該設(shè)為原y表的表尾。 注意：last指針其實只要在表頭結(jié)點中記錄即可，因為每一次查到FIND-SET（x）都可以得到表頭元素。而鏈表中其他元素重新記錄last是無意義的。 我們總是把y接到x里去，那么如果y所在的集合非常大，每次賦值的代價就會非常高，考慮輸入數(shù)據(jù)的特殊性，比如出現(xiàn)輸入為： （2，1），（3，1），（4，1），（5，1），（6，1） ， ，(n

11、,1) 最壞情況下時間復(fù)雜度為O(n2)。,（2）快速實現(xiàn) 上述簡單實現(xiàn)非常不理想，針對y可能比較大的這個問題，可以很快產(chǎn)生一個聰明的想法：不妨比較x和y所在集合的大小，從而作出選擇，把較短的鏈表接在較長的尾部，這樣效果是一樣的，但耗費(fèi)肯定不比原來差。這就是快速實現(xiàn)的思路?？梢栽趎ode里多設(shè)一個域number，用來記錄此條鏈表中成員的個數(shù)。顯然number記錄在表頭元素中即可，將兩表合并的時候，只要將表的number相加，因此維護(hù)起來是非常方便的。 這種快速實現(xiàn)的方法可以稱為加權(quán)啟發(fā)式合并，這里的權(quán)就是指所記錄的number。,可以證明這種方法的效率。當(dāng)有n個元素時，在UNION上的花費(fèi)（即

12、重新賦值的次數(shù)）的上界是O(nlog2n)。因為：考慮一個固定的對象x，當(dāng)x的代表指針（head）被更新時，x必是屬于一個較小的集合，因此，x的代表指針第一次更新后，結(jié)果集合必然至少有2個元素，類似的，下一次更新后，x所在的集合至少有4個元素。繼續(xù)下去，可以發(fā)現(xiàn)，x的代表指針最多被更新log2n次，因為當(dāng)x所在集合元素已經(jīng)等于n以后，不可能再發(fā)生UNION操作。所以，總共有n個元素時，操作的總次數(shù)不超過nlog2n次。這就保證了整個算法的復(fù)雜度是理想的。,并查集的鏈表實現(xiàn)是一種非常容易接受的算法，并且它的效率也是令人滿意的。其實它的思路和數(shù)組完全一樣，所以實際使用較少。,合并兩個集合時的實現(xiàn)過

13、程如下： UNION(x,y) x = FIND-SET(x); y = FIND-SET(y); if x.numbery.number then UNION(x,y) else UNION(y,x); ,我們用有根樹來表示集合，樹中的每個節(jié)點包含集合的一個成員，每棵樹表示一個集合。多個集合形成森林態(tài)，以每棵樹的樹根作為集合的代表，并且根結(jié)點的父結(jié)點指向其自身，樹上的其他結(jié)點都用一個父指針表示它的附屬關(guān)系。 注意：在同一棵樹中的結(jié)點屬于同一個集合，雖然它們在樹中存在父子結(jié)點關(guān)系，但并不意味著它們之間存在從屬關(guān)系。樹的指針起的只是聯(lián)系集合中元素的作用。 在并查集中，每個分離集合對應(yīng)的一棵樹，稱

14、為分離集合樹。整個并查集也就是一棵分離集合森林。,并查集的樹實現(xiàn),如下圖表示了這種關(guān)系，其包含兩個集合b,c,e,h,d,f,g分別以c和f作為代表。,這種樹結(jié)構(gòu)，也可以簡單地用靜態(tài)數(shù)組實現(xiàn)，設(shè)px表示x元素所指向的父親。 MAKE-SET(x)：px=x; FIND-SET(x)：要從x開始，向上尋找它的父親，直到找到根為止。 UNION（x,y）：只要使一棵樹的根指向另一棵樹的根，即成為一棵子樹。,1查找一個元素所屬的集合 在分離集合森林中，每一棵分離集合樹對應(yīng)一個集合。要查找某一元素所屬的集合，就是要找這個元素對應(yīng)的結(jié)點所在的分離集合樹。,查找樹的根結(jié)點的方法很簡單，只需任取樹中一結(jié)點（

15、不妨就取我們要查找的那個結(jié)點），沿父結(jié)點方向一直往樹根走：初始時，取一個結(jié)點，走到它的父結(jié)點，然后以父結(jié)點為基點，走到父結(jié)點的父結(jié)點直至走到一個沒有父結(jié)點的結(jié)點為止，這個結(jié)點就是樹的根結(jié)點。如圖，描述了查找一個結(jié)點的過程（黑色結(jié)點為當(dāng)前查找結(jié)點）。,2兩個元素各自所屬的集合的合并 在分離集合森林中，分離集合是用分離集合樹來表示的。要合并兩個元素各自所屬的集合，也就是合并兩元素所對應(yīng)的兩個結(jié)點各自所在的分離集合樹。,考慮到在分離集合森林中，只要結(jié)點屬于同一棵樹，即被視為在同一個集合中，而不管具體是如何相連的。那么，我們只需簡單的將一棵分離集合樹作為另一棵的子樹，即可使兩棵樹合并為一棵。如圖，描述

16、的是將兩棵分離集合樹D1和D2合并的過程（D1作為D2的根結(jié)點的一棵子樹）。,3優(yōu)化查找與合并算法 優(yōu)化合并過程 如果兩棵分離集合樹A和B，深度分別為hA和hB，則若hAhB，應(yīng)將 B樹作為A樹的子 樹；否則，將A樹 作為B樹的子樹。,優(yōu)化查找過程 對于查找過程有兩個方面的啟發(fā)式方法都很有效，分別是按秩合并和路徑壓縮優(yōu)化。 A按秩合并 進(jìn)行UNION的時候，只要讓具有較小秩的根指向具有較大秩的根。如果兩根的秩相等，只要使其中一個根指向另一個，同時秩應(yīng)當(dāng)增加1。這十分類似于統(tǒng)計節(jié)點個數(shù)，但這里統(tǒng)計的是樹的深度。,B路徑壓縮優(yōu)化方法 在查找一個結(jié)點所在樹的根結(jié)點的過程中，要經(jīng)過一條從待查結(jié)點到根結(jié)

17、點的路徑。我們不妨就讓這些路徑上的結(jié)點直接指向根結(jié)點，作為根結(jié)點的子結(jié)點。這樣，這些路徑上的結(jié)點仍在分離集合中，整棵樹仍然滿足分離集合樹的要求，而路徑上的結(jié)點的深度無疑降低了，這些點及其子樹上的結(jié)點的查找復(fù)雜度大大降低。,如圖，描述了在一棵分離集合樹查找結(jié)點7的前后所呈現(xiàn)出的結(jié)構(gòu)。,優(yōu)化后的代碼： MAKE-SET(x) px=x；rankx=0； UNION(x,y) x = FIND-SET(x)；y=FIND-SET(Y)； if rankx ranky then py=x else px=y； if rankx = ranky then ranky = ranky+1; FIND-SE

18、T(x) if xpx then px=FIND-SET(px)； return px； ,并查集的應(yīng)用,簡單模型基本應(yīng)用 優(yōu)化算法整合應(yīng)用 創(chuàng)新模型綜合應(yīng)用,例2：可愛的猴子(POI2003),一棵樹上有n 只猴子，他們從1到n編號。編號為1 的猴子用它的尾巴盤住了一個樹枝，剩下的猴子要么被其他的猴子鉤住要么就是自己用手鉤住其他的猴子。每只猴子都可以用兩只手去鉤其他的猴子,每只手最多只能鉤一只。從0時刻開始,每一秒都有一只猴子松開它的一只手。這也許會造成一些猴子掉落到地上,我們想要知道它們掉落地上的時間(猴子掉落的速度都非常的快,可以忽略掉落的時間)。,輸入： 第一行包含兩個整數(shù)n和 m,

19、1 = n = 200000, 1 = m = 400000。整數(shù) n 代表猴子總數(shù), 數(shù) m 代表我們觀察猴子的總時間。接下來 n 行描述初始的情形，第 (k + 1) 行 (1 = k = n) 有兩個整數(shù)分別代表猴子k的左手和右手分別抓住了哪兩只猴子，-1 代表它的那只手是空的。 接下來m行代表我們觀察到的猴子的活動，第i行有兩個整數(shù)(1 = i = m) 代表在第i 1時刻放開手的是哪只猴子和它放開的是哪只手(1 左, 2 右)。,輸出： 輸出n個整數(shù)每行一個代表每只猴子掉落到地 上的時間, 如果沒有掉落, 輸出-1. 輸入樣例： 3 2-1 33 -11 21 23 1 輸出樣例：

20、-111,例3：優(yōu)化kruskal算法,Kruskal算法是一種貪心的求最小生成樹的算法，具體操作是初始時所有的邊都是未選邊，圖中只有點，每次選擇一條權(quán)值最小的，連接在不同連通塊的未選邊，然后將這條未選邊賦值為已選邊。 經(jīng)過n-1次操作之后，就求出了該圖的最小生成樹,例4：Ant Trip(HDU3018),Ant Country有N個小鎮(zhèn)，小鎮(zhèn)之間有M條路相連。Ant Tony和朋友們一起想游遍國內(nèi)所有的小鎮(zhèn)，對于每條路他們計劃都要走一遍且只走一遍。然而，這對于一個團(tuán)隊來說，是一個幾乎不可能完成的任務(wù)。因此，他們將分成若干個小組同時進(jìn)行，每個小組可以從不同的小鎮(zhèn)開始旅游，現(xiàn)在，tony 想知

21、道最少需要幾個小組就可以完成這個旅游計劃。,輸入： 輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)之間用一些空行間隔，每組數(shù)據(jù)的第一行有兩個整數(shù)N(1=N=100000),M(0=M=200000),表示Ant Country有N個小鎮(zhèn)和M條路，接下來有M行，每行有兩個整數(shù)a,b,(1=a,b=N)表示小鎮(zhèn) a和小鎮(zhèn)b有一條路。沒有兩條相同的路，也沒有一條路連接同一個小鎮(zhèn)。 對于沒有路連接的小鎮(zhèn)，將直接忽略它。,輸出：對于每組數(shù)據(jù)，輸出完成旅游計劃至少需要的小組數(shù)。 輸入樣例： 3 3 1 2 2 3 1 3 4 2 1 2 3 4,輸出樣例： 1 2,例5：銀河英雄傳說(NOI2002),宇宙歷七九九年，銀河系

22、的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭。泰山壓頂集團(tuán)派宇宙艦隊司令萊因哈特率領(lǐng)十萬余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點名將楊威利組織麾下三萬艘戰(zhàn)艦迎敵。 楊威利擅長排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場劃分成30000列，每列依次編號為1, 2, , 30000。之后，他把自己的戰(zhàn)艦也依次編號為1, 2, , 30000，讓第i號戰(zhàn)艦處于第i列(i = 1, 2, , 30000)，形成“一字長蛇陣”，誘敵深入。這是初始陣形。當(dāng)進(jìn)犯之?dāng)车竭_(dá)時，楊威利會多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，實施密集攻擊。合并指令為M i j，含義為讓第i號戰(zhàn)艦所在

23、的整個戰(zhàn)艦隊列，作為一個整體（頭在前尾在后）接至第j號戰(zhàn)艦所在的戰(zhàn)艦隊列的尾部。顯然戰(zhàn)艦隊列是由處于同一列的一個或多個戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會使隊列增大。,然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動。在交戰(zhàn)中，他可以通過龐大的情報網(wǎng)絡(luò)隨時監(jiān)聽楊威利的艦隊調(diào)動指令。 在楊威利發(fā)布指令調(diào)動艦隊的同時，萊因哈特為了及時了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會發(fā)出一些詢問指令：C i j。該指令意思是，詢問電腦，楊威利的第i號戰(zhàn)艦與第j號戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。 作為一個資深的高級程序設(shè)計員，你被要求編寫程序分析楊威利的指令，以及回答萊因哈特的詢問。,

24、輸入: 輸入文件galaxy.in的第一行有一個整數(shù) T（1=T=500,000），表示總共有T條指令。以下有T行，每行有一條指令。指令有兩種格式： M i j ：i和j是兩個整數(shù)（1=i , j=30000），表示指令涉及的戰(zhàn)艦編號。該指令是萊因哈特竊聽到的楊威利發(fā)布的艦隊調(diào)動指令，并且保證第i號戰(zhàn)艦與第j號戰(zhàn)艦不在同一列。 C i j ：i和j是兩個整數(shù)（1=i , j=30000），表示指令涉及的戰(zhàn)艦編號。該指令是萊因哈特發(fā)布的詢問指令。,輸出: 輸出文件為galaxy.out。你的程序應(yīng)當(dāng)依 次對輸入的每一條指令進(jìn)行分析和處理： 如果是楊威利發(fā)布的艦隊調(diào)動指令，則表示艦 隊排列發(fā)生了變化，你的程序要注意到這一點， 但是不要輸出任何信息； 如果是萊因哈特發(fā)布的詢問指令，你的程序要 輸出一行，僅包含一個整數(shù)，表