我們需要返回一個指針指向該元素x所在的集合
實現方法
一個最自然的想法是使用數組來模擬合并的過程。 定義一個二維數組a[i][j]，i表示第幾個集合，j表示這個集合中的第幾個數。我們可以預見到這樣的數據結構將導致暴力的合并操作（O（n） 的時間復雜度）和詢問操作（同樣是O(n)的時間復雜度，雖然通過加入一個pos[i]數組可以降低為O(1)）。 即使通過一些優化，我們可以把常數降低，但是面對n^2的空間復雜度，我們不得不直接放棄這個想法。
而緊接著的想法就是使用鏈表了。 其實幾乎所有用數組實現的算法都可以使用鏈表實現，雖然時間效率上會有常數上的差異。使用鏈表的話我們需要對每一個元素定義三個值：代表的位置、ID、同集合中的下一個元素位置。這三個值都是必要的， 與數組實現的不同之處就是我們只使用了O（n）的空間。但是合并操作在極端境況下仍需要平均O（n）的復雜度：
合并操作的時候，假設面對兩個集合S1，S2。 我們把S2的所有元素都并入S1中并改變S2的所有元素的“代表的位置”的值，那么我們這次操作的時間復雜度是O（|S2|）。面對開始時候的S1,S2,S3,…,Sn， 假設我們需要進行如下的合并操作：
Union(S2,S1);
Union(S3,S2);
Union(S4,S3);
…
Union(Sn,Sn-1)
那么我們需要O(n^2)的時間來完成這些操作。
下面我們加入一個簡單的啟發策略——加權式啟發策略（Weighted-Union Heuristic）：當每次合并集合的時候，我們總是把元素個數少的集合合并到元素個數多的集合中去。雖然這個啟發策略看起來很弱， 但是可以證明這個策略使Union的平攤時間復雜度降低為O(lgn)。
（以上內容參考《算法導論第二版》（《INTRODUCTION TO ALGORITHMS SECOND EDITION》）第21章：用于不相交集合的數據結構（Data Structures for Disjoint Sets））
更進一步的想法
在推出并查集的想法之前， 我們應該想想我們是如何想到可能有這個想法的存在的（或者說Tarjan是如何想到這個想法的存在的），即，我們之間的樸素想法是否存在冗余？
既然是樸素的算法，那自然是有冗余存在的。 有一個很不錯的想法起源于懶人邏輯：如果有一件事情早做晚做都一樣，那么我寧愿晚做。由于詢問操作的時間復雜度是O（1）的， 所以算法的瓶頸位于合并操作中；而合并操作的時間復雜度由兩部分組成：O（生成新的集合）+O（修改集合代表）。
顯然O（生成新的集合）的時間復雜度是O（1）的， 所以真正的瓶頸位于O（修改集合代表）。
那么， 修改集合代表這個操作會對之后的什么操作有影響呢？
由于我們的目的是應付所有的詢問操作， 即x元素現在位于哪一個集合中。所以，修改x元素的集合代表這個操作，從合并x元素所在集合， 到對x進行詢問操作這段時間內任何時間都可以做而對算法的正確性沒有影響。應用懶人邏輯，我們完全可以先把這個操作記錄下來， 在對x詢問進行詢問操作的時候再處理。
于是，我們就得到了一個森林（Disjoint-set Forest）的結構，森林里的每一棵樹都代表了一個集合。樹的根結點表示這個集合的代表，樹的非根結點則代表了集合中的其余元素。 每一個結點都有一個指針指向了自己所在集合的代表，但是這個指針未必是實時更新的——也就是說， 這個指針指向的元素A可能在某一次合并操作之后不再是代表了。但是由于元素A的指針指向在那次合并操作之后的新的代表B， 而B也會有指針指向代表C……直到某一個元素的指針指向了自己，我們就會知道，這個元素是真正的根結點， 也就是目前的集合的代表。雖然看起來這樣順藤摸瓜很是麻煩，但是這個方法的操作數是小于等于之前的合并操作使用的操作數的（ 有些沒有被詢問到的元素的指針就永遠不會被更新）。
懶人的方法自然要優秀一點，但也并不優秀到哪里去。 因為目前的方法并沒有真正降低算法的時間復雜度。但是我們將看到，在這個新的數據結構中，通過加入兩個優秀的啟發式策略，我們將獲得目前已知的、 漸近意義上最快的不相交集合的數據結構。
樹的優勢
在提出這兩個啟發式策略之前，我們不妨自己考慮一下， 有什么樣的啟發式策略可以加入這個森林的結構呢？作為與數組、鏈表不同的樹結構，它到底有什么方面的優勢呢？ 雖然看起來獨立地創造出這些策略并不是我輩能力所及，但其實并非如此。事實上，遠在Tarjan正式地證明并查集的時間復雜度（1975） 之前的六十年代，很多程序員都會在自己的程序中加入這些啟發式策略，因為這些策略幫助他們的程序更加快速地運行， 只是大家都不知道這些策略到底多么有效，它們在最壞情況下會有什么樣子的表現。因此如果僅僅是提出策略而不證明，我們完全是有這個能力的。
這里，我們再度搬出懶人邏輯。 其實懶人邏輯的本質是消除冗余，而正如某人說過的，提高效率的關鍵就是消除冗余。在不斷地消除冗余的過程中，我們將一步步地提高程序效率。
首先，受到之前的加權式啟發策略的影響， 我們可以考慮到，在這個森林結構中也可以加入一個類似的啟發策略。我們知道給樹加權常用兩種方法，一種是以樹的高度為標準的； 一種是以樹的結點個數為標準的。我個人是傾向于以樹的結點個數為標準的加權策略，但是Tarjan給出的啟發式策略是以樹的高度為標準的， 叫做按秩合并（Union by Rank）。（這里我一直有一個疑問，因為我覺得以樹的結點個數為標準效果不會比以樹的高度為標準差。 我查閱的資料中沒有什么明確的答案，貌似是因為以高度為標準的時候，算法的時間復雜度更加容易計算。就我個人多年的實踐經驗而言， 我一直是使用按照結點個數為標準的啟發函數的，而執行效率不比標準算法差，甚至在某些測試中表現更加優秀。）
具體的按秩合并的操作是這樣的： 剛開始的時候每一棵樹的秩都是0。當執行合并操作的時候，如果即將合并的兩棵樹的秩是相等的，任選一顆樹的根作為新的根合并，并且把這棵樹的秩加1； 否則選擇秩更大的樹的根作為新的根，秩不變。秩的定義是，這棵樹的根結點到葉結點的路徑的最大長度的上界。（ 也就是樹的深度的上界，但由于有了路徑壓縮的啟發式策略，未必是上確界）
既然這個啟發策略和之前的加權式啟發策略類似， 我們自然不能指望它的效率能夠有大幅上漲。事實上，它的均攤時間復雜度仍然是O(lgn)的。我們需要更強的啟發式策略。
考慮詢問操作時，針對某一個結點的“順藤摸瓜”找代表時的具體操作。我們必須清醒地意識到， 所有的時間復雜度來源于這一順藤摸瓜的過程，而要提高算法效率的關鍵也就在這里。
有一個非常簡單的想法就是，每次順藤摸瓜的過程中， 摸到的每一個結點，都是在同一個集合中的；而這些結點的代表自然也就是最后找到的根結點。我們可以把這些結點的指針全部都指向該根結點，這樣， 以后進行詢問操作順藤摸瓜的時候，一旦摸到了這些結點中的某一個，我們就不需要繼續摸這么長的藤，可以直接跳到根結點（ 當然這個時侯這個根結點可能已經變成非根結點了）。
這兩個啟發式策略就是這么簡單。但是我們可以證明， 使用了這兩個啟發式策略之后，最壞情況下的時間復雜度為O(mа(n))，其中а(n)是一個增長極端緩慢的函數， 在任何我們可以想象到的情況中，а(n)都不會超過4。 因此我們認為這個算法的時間復雜度幾乎是線性的。
精準的時間復雜度分析
1.Ackermann函數和它的反函數
2.秩的性質
（請注意將這里的秩的性質，和在另一種啟發式策略， 即以結點個數為標準的策略中，樹的結點個數的性質進行比較，它們共有這些性質）
對于所有的結點x而言，rank[x]≤rank[p[x]]，其中p[x]表示x的指針指向的結點。 當且僅當x為根結點的時候可以取到等號。并且，rank[x]從初始值0開始嚴格遞增，一直到x不再是根結點的時候為止。 從此之后，rank[x]不再變化。
從任何一個結點指向根的路徑上，結點的秩是嚴格遞增的
每個結點的秩最多為n-1。
應用題解：食物鏈
動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B， B吃C，C吃A。
現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。
有人用兩種說法對這N個動物所構成的食物鏈關系進行描述：
第一種說法是“1 X Y”，表示X和Y是同類。
第二種說法是“2 X Y”，表示X吃Y。
此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。
1） 當前的話與前面的某些真的話沖突，就是假話；
2） 當前的話中X或Y比N大，就是假話；
3） 當前的話表示X吃X，就是假話。
你的任務是根據給定的N（1<=N<=50,000）和K句話（0<=K<=100,000），輸出假話的總數。
輸入文件（eat.in）
第一行是兩個整數N和K，以一個空格分隔。
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。
輸出文件（eat.out）
只有一個整數，表示假話的數目。
輸入樣例
|
輸入文件 |
對7句話的分析 |
|
100 7 |
|
|
1 101 1 |
假話 |
|
2 1 2 |
真話 |
|
2 2 3 |
真話 |
|
2 3 3 |
假話 |
|
1 1 3 |
假話 |
|
2 3 1 |
真話 |
|
1 5 5 |
真話 |
輸出樣例
3
| 歡迎光臨 (http://www.raoushi.com/bbs/) |
Powered by Discuz! X3.1 |