并查集（Disjoint-set Forests）

ID:107189 · 發(fā)表于 2016-3-5 18:13

算法起源

我們可能會(huì)遇到一些問題（including handling EQUIVALENCE and COMMON statements in FORTRAN , finding minimum spanning trees, computing dominators in directed graphs, checking flow graphs for reducibility, calculating depths in trees, computing least common ancestors in trees, and solving an offline minimum problem，以上摘自《Efficiency of a Good But Not Linear Set Union Algorithm》, ROBERT ENDRE TARJAN），與將n個(gè)不同的元素合并為一些不相交集合（Disjoint Sets）有關(guān)。這種問題往往包含兩種操作，一種是所謂的詢問操作（Find），即尋找某一個(gè)元素當(dāng)前在哪一個(gè)集合中；另一種則是合并操作（Union），把某兩個(gè)集合合并為一個(gè)集合（開始的時(shí)候n個(gè)元素即為n個(gè)集合）。我們需要有效的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)這兩種操作。
　

一個(gè)有用的想法

我們很難尋找到一個(gè)集合的簡單的表示方法——集合的最小表示時(shí)間復(fù)雜度過高，而且在這個(gè)問題中并不實(shí)用。事實(shí)上，由于這里的集合都是不相交的，因此我們可以使用集合中的任意一個(gè)元素作為這個(gè)集合的代表（Representative）來唯一地確定這個(gè)集合。這樣不僅簡化了集合的表示，而且我們之后可以看到，它將起到非常重要的作用。

以下是使用了代表表示法之后，幾種操作的簡單實(shí)現(xiàn)方法：

生成集合（Make-Set）：對(duì)于新加入的某一個(gè)元素x，在確認(rèn)它不在已有集合之中之后，我們可以生成一個(gè)新的集合，并且將x作為這個(gè)集合的代表
合并集合（Union）：合并某兩個(gè)集合S1，S2。我們合并這兩個(gè)集合形成新的集合S3=S1 U S2，并且刪去S1和S2。雖然S3的代表可以是S1 U S2中的任意一個(gè)，但是我們一般從S1的代表和S2的代表中任選一個(gè)作為S3的代表
詢問操作（Find-Set）：對(duì)于某一個(gè)元素x，我們需要返回一個(gè)指針指向該元素x所在的集合

　
實(shí)現(xiàn)方法

一個(gè)最自然的想法是使用數(shù)組來模擬合并的過程。定義一個(gè)二維數(shù)組a[i][j]，i表示第幾個(gè)集合，j表示這個(gè)集合中的第幾個(gè)數(shù)。我們可以預(yù)見到這樣的數(shù)據(jù)結(jié)構(gòu)將導(dǎo)致暴力的合并操作（O（n）的時(shí)間復(fù)雜度）和詢問操作（同樣是O(n)的時(shí)間復(fù)雜度，雖然通過加入一個(gè)pos[i]數(shù)組可以降低為O(1)）。即使通過一些優(yōu)化，我們可以把常數(shù)降低，但是面對(duì)n^2的空間復(fù)雜度，我們不得不直接放棄這個(gè)想法。

而緊接著的想法就是使用鏈表了。其實(shí)幾乎所有用數(shù)組實(shí)現(xiàn)的算法都可以使用鏈表實(shí)現(xiàn)，雖然時(shí)間效率上會(huì)有常數(shù)上的差異。使用鏈表的話我們需要對(duì)每一個(gè)元素定義三個(gè)值：代表的位置、ID、同集合中的下一個(gè)元素位置。這三個(gè)值都是必要的，與數(shù)組實(shí)現(xiàn)的不同之處就是我們只使用了O（n）的空間。但是合并操作在極端境況下仍需要平均O（n）的復(fù)雜度：

合并操作的時(shí)候，假設(shè)面對(duì)兩個(gè)集合S1，S2。我們把S2的所有元素都并入S1中并改變S2的所有元素的“代表的位置”的值，那么我們這次操作的時(shí)間復(fù)雜度是O（|S2|）。面對(duì)開始時(shí)候的S1,S2,S3,…,Sn，假設(shè)我們需要進(jìn)行如下的合并操作：

Union(S2,S1);

Union(S3,S2);

Union(S4,S3);

…

Union(Sn,Sn-1)

那么我們需要O(n^2)的時(shí)間來完成這些操作。
　

下面我們加入一個(gè)簡單的啟發(fā)策略——加權(quán)式啟發(fā)策略（Weighted-Union Heuristic）：當(dāng)每次合并集合的時(shí)候，我們總是把元素個(gè)數(shù)少的集合合并到元素個(gè)數(shù)多的集合中去。雖然這個(gè)啟發(fā)策略看起來很弱，但是可以證明這個(gè)策略使Union的平攤時(shí)間復(fù)雜度降低為O(lgn)。

　

（以上內(nèi)容參考《算法導(dǎo)論第二版》（《INTRODUCTION TO ALGORITHMS SECOND EDITION》）第21章：用于不相交集合的數(shù)據(jù)結(jié)構(gòu)（Data Structures for Disjoint Sets））

　

更進(jìn)一步的想法

在推出并查集的想法之前，我們應(yīng)該想想我們是如何想到可能有這個(gè)想法的存在的（或者說Tarjan是如何想到這個(gè)想法的存在的），即，我們之間的樸素想法是否存在冗余？

既然是樸素的算法，那自然是有冗余存在的。有一個(gè)很不錯(cuò)的想法起源于懶人邏輯：如果有一件事情早做晚做都一樣，那么我寧愿晚做。由于詢問操作的時(shí)間復(fù)雜度是O（1）的，所以算法的瓶頸位于合并操作中；而合并操作的時(shí)間復(fù)雜度由兩部分組成：O（生成新的集合）+O（修改集合代表）。

顯然O（生成新的集合）的時(shí)間復(fù)雜度是O（1）的，所以真正的瓶頸位于O（修改集合代表）。

那么，修改集合代表這個(gè)操作會(huì)對(duì)之后的什么操作有影響呢？

由于我們的目的是應(yīng)付所有的詢問操作，即x元素現(xiàn)在位于哪一個(gè)集合中。所以，修改x元素的集合代表這個(gè)操作，從合并x元素所在集合，到對(duì)x進(jìn)行詢問操作這段時(shí)間內(nèi)任何時(shí)間都可以做而對(duì)算法的正確性沒有影響。應(yīng)用懶人邏輯，我們完全可以先把這個(gè)操作記錄下來，在對(duì)x詢問進(jìn)行詢問操作的時(shí)候再處理。

于是，我們就得到了一個(gè)森林（Disjoint-set Forest）的結(jié)構(gòu)，森林里的每一棵樹都代表了一個(gè)集合。樹的根結(jié)點(diǎn)表示這個(gè)集合的代表，樹的非根結(jié)點(diǎn)則代表了集合中的其余元素。每一個(gè)結(jié)點(diǎn)都有一個(gè)指針指向了自己所在集合的代表，但是這個(gè)指針未必是實(shí)時(shí)更新的——也就是說，這個(gè)指針指向的元素A可能在某一次合并操作之后不再是代表了。但是由于元素A的指針指向在那次合并操作之后的新的代表B，而B也會(huì)有指針指向代表C……直到某一個(gè)元素的指針指向了自己，我們就會(huì)知道，這個(gè)元素是真正的根結(jié)點(diǎn)，也就是目前的集合的代表。雖然看起來這樣順藤摸瓜很是麻煩，但是這個(gè)方法的操作數(shù)是小于等于之前的合并操作使用的操作數(shù)的（有些沒有被詢問到的元素的指針就永遠(yuǎn)不會(huì)被更新）。

懶人的方法自然要優(yōu)秀一點(diǎn)，但也并不優(yōu)秀到哪里去。因?yàn)槟壳暗姆椒ú]有真正降低算法的時(shí)間復(fù)雜度。但是我們將看到，在這個(gè)新的數(shù)據(jù)結(jié)構(gòu)中，通過加入兩個(gè)優(yōu)秀的啟發(fā)式策略，我們將獲得目前已知的、漸近意義上最快的不相交集合的數(shù)據(jù)結(jié)構(gòu)。
　

樹的優(yōu)勢(shì)

在提出這兩個(gè)啟發(fā)式策略之前，我們不妨自己考慮一下，有什么樣的啟發(fā)式策略可以加入這個(gè)森林的結(jié)構(gòu)呢？作為與數(shù)組、鏈表不同的樹結(jié)構(gòu)，它到底有什么方面的優(yōu)勢(shì)呢？雖然看起來獨(dú)立地創(chuàng)造出這些策略并不是我輩能力所及，但其實(shí)并非如此。事實(shí)上，遠(yuǎn)在Tarjan正式地證明并查集的時(shí)間復(fù)雜度（1975）之前的六十年代，很多程序員都會(huì)在自己的程序中加入這些啟發(fā)式策略，因?yàn)檫@些策略幫助他們的程序更加快速地運(yùn)行，只是大家都不知道這些策略到底多么有效，它們?cè)谧顗那闆r下會(huì)有什么樣子的表現(xiàn)。因此如果僅僅是提出策略而不證明，我們完全是有這個(gè)能力的。

這里，我們?cè)俣劝岢鰬腥诉壿嫛?wbr> 其實(shí)懶人邏輯的本質(zhì)是消除冗余，而正如某人說過的，提高效率的關(guān)鍵就是消除冗余。在不斷地消除冗余的過程中，我們將一步步地提高程序效率。

首先，受到之前的加權(quán)式啟發(fā)策略的影響，我們可以考慮到，在這個(gè)森林結(jié)構(gòu)中也可以加入一個(gè)類似的啟發(fā)策略。我們知道給樹加權(quán)常用兩種方法，一種是以樹的高度為標(biāo)準(zhǔn)的；一種是以樹的結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)的。我個(gè)人是傾向于以樹的結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)的加權(quán)策略，但是Tarjan給出的啟發(fā)式策略是以樹的高度為標(biāo)準(zhǔn)的，叫做按秩合并（Union by Rank）。（這里我一直有一個(gè)疑問，因?yàn)槲矣X得以樹的結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)效果不會(huì)比以樹的高度為標(biāo)準(zhǔn)差。我查閱的資料中沒有什么明確的答案，貌似是因?yàn)橐愿叨葹闃?biāo)準(zhǔn)的時(shí)候，算法的時(shí)間復(fù)雜度更加容易計(jì)算。就我個(gè)人多年的實(shí)踐經(jīng)驗(yàn)而言，我一直是使用按照結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)的啟發(fā)函數(shù)的，而執(zhí)行效率不比標(biāo)準(zhǔn)算法差，甚至在某些測(cè)試中表現(xiàn)更加優(yōu)秀。）

具體的按秩合并的操作是這樣的：剛開始的時(shí)候每一棵樹的秩都是0。當(dāng)執(zhí)行合并操作的時(shí)候，如果即將合并的兩棵樹的秩是相等的，任選一顆樹的根作為新的根合并，并且把這棵樹的秩加1；否則選擇秩更大的樹的根作為新的根，秩不變。秩的定義是，這棵樹的根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑的最大長度的上界。（也就是樹的深度的上界，但由于有了路徑壓縮的啟發(fā)式策略，未必是上確界）

既然這個(gè)啟發(fā)策略和之前的加權(quán)式啟發(fā)策略類似，我們自然不能指望它的效率能夠有大幅上漲。事實(shí)上，它的均攤時(shí)間復(fù)雜度仍然是O(lgn)的。我們需要更強(qiáng)的啟發(fā)式策略。

考慮詢問操作時(shí)，針對(duì)某一個(gè)結(jié)點(diǎn)的“順藤摸瓜”找代表時(shí)的具體操作。我們必須清醒地意識(shí)到，所有的時(shí)間復(fù)雜度來源于這一順藤摸瓜的過程，而要提高算法效率的關(guān)鍵也就在這里。

有一個(gè)非常簡單的想法就是，每次順藤摸瓜的過程中，摸到的每一個(gè)結(jié)點(diǎn)，都是在同一個(gè)集合中的；而這些結(jié)點(diǎn)的代表自然也就是最后找到的根結(jié)點(diǎn)。我們可以把這些結(jié)點(diǎn)的指針全部都指向該根結(jié)點(diǎn)，這樣，以后進(jìn)行詢問操作順藤摸瓜的時(shí)候，一旦摸到了這些結(jié)點(diǎn)中的某一個(gè)，我們就不需要繼續(xù)摸這么長的藤，可以直接跳到根結(jié)點(diǎn)（當(dāng)然這個(gè)時(shí)侯這個(gè)根結(jié)點(diǎn)可能已經(jīng)變成非根結(jié)點(diǎn)了）。

這兩個(gè)啟發(fā)式策略就是這么簡單。但是我們可以證明，使用了這兩個(gè)啟發(fā)式策略之后，最壞情況下的時(shí)間復(fù)雜度為O(mа(n))，其中а(n)是一個(gè)增長極端緩慢的函數(shù)，在任何我們可以想象到的情況中，а(n)都不會(huì)超過4。因此我們認(rèn)為這個(gè)算法的時(shí)間復(fù)雜度幾乎是線性的。
　

精準(zhǔn)的時(shí)間復(fù)雜度分析

1.Ackermann函數(shù)和它的反函數(shù)

2.秩的性質(zhì)

（請(qǐng)注意將這里的秩的性質(zhì)，和在另一種啟發(fā)式策略，即以結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)的策略中，樹的結(jié)點(diǎn)個(gè)數(shù)的性質(zhì)進(jìn)行比較，它們共有這些性質(zhì)）

對(duì)于所有的結(jié)點(diǎn)x而言，rank[x]≤rank[p[x]]，其中p[x]表示x的指針指向的結(jié)點(diǎn)。當(dāng)且僅當(dāng)x為根結(jié)點(diǎn)的時(shí)候可以取到等號(hào)。并且，rank[x]從初始值0開始嚴(yán)格遞增，一直到x不再是根結(jié)點(diǎn)的時(shí)候?yàn)橹埂?wbr> 從此之后，rank[x]不再變化。
從任何一個(gè)結(jié)點(diǎn)指向根的路徑上，結(jié)點(diǎn)的秩是嚴(yán)格遞增的
每個(gè)結(jié)點(diǎn)的秩最多為n-1。

應(yīng)用題解：食物鏈

動(dòng)物王國中有三類動(dòng)物A,B,C，這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B， B吃C，C吃A。

現(xiàn)有N個(gè)動(dòng)物，以1－N編號(hào)。每個(gè)動(dòng)物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。

有人用兩種說法對(duì)這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：

第一種說法是“1 X Y”，表示X和Y是同類。

第二種說法是“2 X Y”，表示X吃Y。

此人對(duì)N個(gè)動(dòng)物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。

1）當(dāng)前的話與前面的某些真的話沖突，就是假話；

2）當(dāng)前的話中X或Y比N大，就是假話；

3）當(dāng)前的話表示X吃X，就是假話。

你的任務(wù)是根據(jù)給定的N（1<=N<=50,000）和K句話（0<=K<=100,000），輸出假話的總數(shù)。

輸入文件（eat.in）