清北學(xué)堂講義06朱全民并查集

1、并查集Yali 朱全民分離集合在有的問(wèn)題中，需要對(duì)不相交的集合(disjoint set)進(jìn)行這樣兩種操作：檢索某元素屬于哪個(gè)集合合并兩個(gè)集合能夠維護(hù)這兩個(gè)操作的數(shù)據(jù)結(jié)構(gòu)，我們稱之為并查集。并查集的森林實(shí)現(xiàn)一般來(lái)說(shuō)我們用森林的結(jié)構(gòu)實(shí)現(xiàn)并查集在森林中，每棵樹(shù)代表一個(gè)集合。用樹(shù)根來(lái)表示這個(gè)集合。合并操作：兩個(gè)集合S1、S2合并，將其中的一個(gè)樹(shù)根作為另一個(gè)樹(shù)根的子樹(shù)即可。查找操作：對(duì)于一個(gè)元素u的查找，順著u往上找，直到線索到根節(jié)點(diǎn)，也就確定了u所在的集合。兩個(gè)優(yōu)化啟發(fā)式合并： 在合并集合S1、S2的時(shí)候，我們讓較小的樹(shù)成為較大的樹(shù)的子樹(shù)。這里可以是深度、節(jié)點(diǎn)個(gè)數(shù)等啟發(fā)函數(shù)來(lái)比較樹(shù)的大小。路徑壓縮：

2、 我們?cè)诓檎彝陁至根節(jié)點(diǎn)的路徑之后，一般將這條路徑上的所有節(jié)點(diǎn)的父節(jié)點(diǎn)都設(shè)為根節(jié)點(diǎn)，這樣可以大大減少之后的查找次數(shù)。并查集的時(shí)間復(fù)雜度可以證明，經(jīng)過(guò)啟發(fā)式合并和路徑壓縮之后的并查集，執(zhí)行m次查找的復(fù)雜度為O(m(m)其中(m)是Ackermann函數(shù)的某個(gè)反函數(shù)，你可以近似的認(rèn)為它是小于5的。所以并查集的單次查找操作的時(shí)間復(fù)雜度也幾乎是常數(shù)級(jí)的。例一 銀河英雄傳說(shuō)(NOI2002) 宇宙歷七九九年，銀河系的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭(zhēng)。泰山壓頂集團(tuán)派宇宙艦隊(duì)司令萊因哈特率領(lǐng)十萬(wàn)余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊威利組織麾下三萬(wàn)艘戰(zhàn)艦迎敵。 楊威利擅長(zhǎng)排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多

3、，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(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í)施密集攻擊。合并指令為M i j，含義為讓第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ì)列增大。例一 銀河英雄傳說(shuō)(NOI20

4、02) 然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動(dòng)。在交戰(zhàn)中，他可以通過(guò)龐大的情報(bào)網(wǎng)絡(luò)隨時(shí)監(jiān)聽(tīng)楊威利的艦隊(duì)調(diào)動(dòng)指令。 在楊威利發(fā)布指令調(diào)動(dòng)艦隊(duì)的同時(shí)，萊因哈特為了及時(shí)了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會(huì)發(fā)出一些詢問(wèn)指令：C i j。該指令意思是，詢問(wèn)電腦，楊威利的第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。 作為一個(gè)資深的高級(jí)程序設(shè)計(jì)員，你被要求編寫(xiě)程序分析楊威利的指令，以及回答萊因哈特的詢問(wèn)。例一 銀河英雄傳說(shuō)(NOI2002)觀察這個(gè)題目，開(kāi)始時(shí)每條戰(zhàn)艦作為獨(dú)立的隊(duì)列。隨著M命令的發(fā)布，分離的隊(duì)列不斷合并。而且途中我們需要知道一些元素（戰(zhàn)艦）的信

5、息這些性質(zhì)啟發(fā)我們應(yīng)用并查集的數(shù)據(jù)結(jié)構(gòu)解決例一 銀河英雄傳說(shuō)(NOI2002)由于我們要得到的信息除了某條戰(zhàn)艦在哪個(gè)隊(duì)列，還要知道它在該隊(duì)列中的位置。因此需要對(duì)并查集進(jìn)行擴(kuò)充。定義：ai：戰(zhàn)艦i暫時(shí)標(biāo)記為屬于以戰(zhàn)艦ai為首的隊(duì)列，稱戰(zhàn)艦ai為戰(zhàn)艦i的父節(jié)點(diǎn)bi：戰(zhàn)艦i到戰(zhàn)艦ai（包括戰(zhàn)艦ai）之間的戰(zhàn)艦數(shù)量，稱bi為戰(zhàn)艦i到戰(zhàn)艦ai的深度。ci：戰(zhàn)艦i所屬隊(duì)列后方（包括戰(zhàn)艦i本身）的戰(zhàn)艦數(shù)量（注意：此變量只有當(dāng)ai=i時(shí)才有意義），稱ci為隊(duì)列長(zhǎng)度。例一 銀河英雄傳說(shuō)(NOI2002)初始時(shí)：ai=i，bi=0，ci=1對(duì)于每個(gè)M i j命令，需要進(jìn)行如下操作：對(duì)戰(zhàn)艦i,j進(jìn)行查找和路徑壓縮設(shè)

6、ai=r1,aj=r2且r1r2，則：ar1=r2，br1=cr2，cr2=cr1+cr2對(duì)于每個(gè)C i j命令，需要進(jìn)行如下操作：對(duì)戰(zhàn)艦i,j進(jìn)行查找和路徑壓縮判斷是否有ai=aj，如是則表示他們是同一隊(duì)列，輸出|bi-bj|-1；如果不是則輸出-1例一 銀河英雄傳說(shuō)(NOI2002)關(guān)于戰(zhàn)艦i的路徑壓縮的步驟：從i出發(fā)尋找根root，并累計(jì)從i到根root的深度，得到bi再次遍歷從i出發(fā)到root的路徑。對(duì)于途中的每一個(gè)節(jié)點(diǎn)k（假設(shè)在修改k之前ak=a1,bk=b1)，則我們根據(jù)已經(jīng)修改過(guò)的戰(zhàn)艦k的a、b值對(duì)戰(zhàn)艦a1的a、b值進(jìn)行修改，即： aa1=root，ba1=bk-b1例一 銀河英

7、雄傳說(shuō)(NOI2002)結(jié)合并查集的時(shí)間復(fù)雜度的理論，可以得到該算法的時(shí)間復(fù)雜度大約為O(K)本題我們對(duì)并查集模型本身進(jìn)行巧妙的修改，得到了高效地解決辦法。下面我們來(lái)看一個(gè)對(duì)問(wèn)題的形式進(jìn)行修改，使得它能夠應(yīng)用并查集的例子。例二 可愛(ài)的猴子(POI2003)樹(shù)上掛著n只可愛(ài)的猴子，編號(hào)為1,n (2=n=200 000)。猴子1的尾巴掛在樹(shù)上，每只猴子有兩只手，每只手可以最多抓住一只猴子的尾巴。所有的猴子都是懸空的，因此如果一旦脫離了樹(shù)，猴子會(huì)立刻掉到地上。第0,1,m(1=m=400000)秒鐘每一秒都有某個(gè)猴子把它的某只手松開(kāi)，因此常常有猴子掉到地上?，F(xiàn)在請(qǐng)你根據(jù)這些信息，計(jì)算出每個(gè)猴子掉在

8、地上的時(shí)間。例二 可愛(ài)的猴子(POI2003)如果把連在一起的猴子看成一個(gè)集合，每次松手就是斷開(kāi)了集合之間的某些聯(lián)系或者直接將一個(gè)集合分離成兩個(gè)。我們要求的是每只猴子第一次脫離猴子1所在集合的時(shí)間?！胺植榧?？例二 可愛(ài)的猴子(POI2003)我們不妨反過(guò)來(lái)想，如果時(shí)間從第m秒開(kāi)始倒流，則出現(xiàn)的情形就是不斷有某只猴子的手抓住另一只猴子。則我們要求的就轉(zhuǎn)化成了：每只猴子最開(kāi)始在什么時(shí)候合并到猴子1所在的集合。這樣就可以應(yīng)用并查集了。例二 可愛(ài)的猴子(POI2003)設(shè)在第t秒鐘，猴子i抓?。▽?shí)際上是放開(kāi)）了猴子j，那么此時(shí)就將i所在的集合與j所在的集合合并。如果需要合并，并且原先猴子i與猴子 j在同一個(gè)集合，那么就將猴子j所在集合的所有猴子掉落的時(shí)刻都是t為了枚舉某一個(gè)集合里的所