我們可能會(huì)遇到一些問(wèn)題（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)。這種問(wèn)題往往包含兩種操作， 一種是所謂的詢問(wèn)操作（Find），即尋找某一個(gè)元素當(dāng)前在哪一個(gè)集合中；另一種則是合并操作（Union），把某兩個(gè)集合合并為一個(gè)集合（ 開(kāi)始的時(shí)候n個(gè)元素即為n個(gè)集合）。我們需要有效的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)這兩種操作。 
　

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

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

    一個(gè)最自然的想法是使用數(shù)組來(lái)模擬合并的過(guò)程。 定義一個(gè)二維數(shù)組a[i][j]，i表示第幾個(gè)集合，j表示這個(gè)集合中的第幾個(gè)數(shù)。我們可以預(yù)見(jiàn)到這樣的數(shù)據(jù)結(jié)構(gòu)將導(dǎo)致暴力的合并操作（O（n） 的時(shí)間復(fù)雜度）和詢問(wèn)操作（同樣是O(n)的時(shí)間復(fù)雜度，雖然通過(guò)加入一個(gè)pos[i]數(shù)組可以降低為O(1)）。 即使通過(guò)一些優(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ì)開(kāi)始時(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í)間來(lái)完成這些操作。 
　

    下面我們加入一個(gè)簡(jiǎn)單的啟發(fā)策略——加權(quán)式啟發(fā)策略（Weighted-Union Heuristic）：當(dāng)每次合并集合的時(shí)候，我們總是把元素個(gè)數(shù)少的集合合并到元素個(gè)數(shù)多的集合中去。雖然這個(gè)啟發(fā)策略看起來(lái)很弱， 但是可以證明這個(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）） 
 
　

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

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

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

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

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

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

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

    在提出這兩個(gè)啟發(fā)式策略之前，我們不妨自己考慮一下， 有什么樣的啟發(fā)式策略可以加入這個(gè)森林的結(jié)構(gòu)呢？作為與數(shù)組、鏈表不同的樹(shù)結(jié)構(gòu)，它到底有什么方面的優(yōu)勢(shì)呢？ 雖然看起來(lái)獨(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ì)是消除冗余，而正如某人說(shuō)過(guò)的，提高效率的關(guān)鍵就是消除冗余。在不斷地消除冗余的過(guò)程中，我們將一步步地提高程序效率。

    首先，受到之前的加權(quán)式啟發(fā)策略的影響， 我們可以考慮到，在這個(gè)森林結(jié)構(gòu)中也可以加入一個(gè)類似的啟發(fā)策略。我們知道給樹(shù)加權(quán)常用兩種方法，一種是以樹(shù)的高度為標(biāo)準(zhǔn)的； 一種是以樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)的。我個(gè)人是傾向于以樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)的加權(quán)策略，但是Tarjan給出的啟發(fā)式策略是以樹(shù)的高度為標(biāo)準(zhǔn)的， 叫做按秩合并（Union by Rank）。（這里我一直有一個(gè)疑問(wèn)，因?yàn)槲矣X(jué)得以樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為標(biāo)準(zhǔn)效果不會(huì)比以樹(shù)的高度為標(biāo)準(zhǔn)差。 我查閱的資料中沒(méi)有什么明確的答案，貌似是因?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)秀。）

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

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

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

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

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

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

2.秩的性質(zhì)

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

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

動(dòng)物王國(guó)中有三類動(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中的一種，但是我們并不知道它到底是哪一種。

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

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

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

此人對(duì)N個(gè)動(dòng)物，用上述兩種說(shuō)法，一句接一句地說(shuō)出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）

第一行是兩個(gè)整數(shù)N和K，以一個(gè)空格分隔。

以下K行每行是三個(gè)正整數(shù) D，X，Y，兩數(shù)之間用一個(gè)空格隔開(kāi)，其中D表示說(shuō)法的種類。

  若D=1，則表示X和Y是同類。

  若D=2，則表示X吃Y。

輸出文件（eat.out）

只有一個(gè)整數(shù)，表示假話的數(shù)目。

輸入樣例

輸出樣例

3