零基礎(chǔ)學(xué)并查集算法

并查集是我暑假從高手那里學(xué)到的一招，覺得真是太精妙的設(shè)計了。以前我無法解決的一類問題竟然可以用如此簡單高效的方法搞定。不分享出來真是對不起party了。（party：我靠，關(guān)我嘛事??？我跟你很熟么？）

來看一個實例，杭電1232暢通工程

首先在地圖上給你若干個城鎮(zhèn)，這些城鎮(zhèn)都可以看作點，然后告訴你哪些對城鎮(zhèn)之間是有道路直接相連的。最后要解決的是整幅圖的連通性問題。比如隨意給你兩個點，讓你判斷它們是否連通，或者問你整幅圖一共有幾個連通分支，也就是被分成了幾個互相獨立的塊。像暢通工程這題，問還需要修幾條路，實質(zhì)就是求有幾個連通分支。如果是1個連通分支，說明整幅圖上的點都連起來了，不用再修路了；如果是2個連通分支，則只要再修1條路，從兩個分支中各選一個點，把它們連起來，那么所有的點都是連起來的了；如果是3個連通分支，則只要再修兩條路……

以下面這組數(shù)據(jù)輸入數(shù)據(jù)來說明

4 2 1 3 4 3

第一行告訴你，一共有4個點，2條路。下面兩行告訴你，1、3之間有條路，4、3之間有條路。那么整幅圖就被分成了1-3-4和2兩部分。只要再加一條路，把2和其他任意一個點連起來，暢通工程就實現(xiàn)了，那么這個這組數(shù)據(jù)的輸出結(jié)果就是1。好了，現(xiàn)在編程實現(xiàn)這個功能吧，城鎮(zhèn)有幾百個，路有不知道多少條，而且可能有回路。 這可如何是好？

我以前也不會呀，自從用了并查集之后，嗨，效果還真好！我們?nèi)叶加盟?/span>

并查集由一個整數(shù)型的數(shù)組和兩個函數(shù)構(gòu)成。數(shù)組pre[]記錄了每個點的前導(dǎo)點是什么，函數(shù)find是查找，join是合并。

int pre[1000 ];

int find(int x)                                                                                                         //查找根節(jié)點

{ 

    int r=x;

    while ( pre[r ] != r )                                                                                              //返回根節(jié)點 r

          r=pre[r ];

    int i=x , j ;

    while( i != r )                                                                                                        //路徑壓縮

    {

         j = pre[ i ]; // 在改變上級之前用臨時變量  j 記錄下他的值 

         pre[ i ]= r ; //把上級改為根節(jié)點

         i=j;

    }

    return r ;

}

void join(int x,int y)                                                                                                    //判斷x y是否連通，

                                                                                             //如果已經(jīng)連通，就不用管了 //如果不連通，就把它們所在的連通分支合并起,

{

    int fx=find(x),fy=find(y);

    if(fx!=fy)

        pre[fx ]=fy;

}

為了解釋并查集的原理，我將舉一個更有愛的例子。 話說江湖上散落著各式各樣的大俠，有上千個之多。他們沒有什么正當職業(yè)，整天背著劍在外面走來走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個優(yōu)點就是講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，只要是能通過朋友關(guān)系串聯(lián)起來的，不管拐了多少個彎，都認為是自己人。這樣一來，江湖上就形成了一個一個的群落，通過兩兩之間的朋友關(guān)系串聯(lián)起來。而不在同一個群落的人，無論如何都無法通過朋友關(guān)系連起來，于是就可以放心往死了打。但是兩個原本互不相識的人，如何判斷是否屬于一個朋友圈呢？

我們可以在每個朋友圈內(nèi)推舉出一個比較有名望的人，作為該圈子的代表人物，這樣，每個圈子就可以這樣命名“齊達內(nèi)朋友之隊”“羅納爾多朋友之隊”……兩人只要互相對一下自己的隊長是不是同一個人，就可以確定敵友關(guān)系了。

但是還有問題啊，大俠們只知道自己直接的朋友是誰，很多人壓根就不認識隊長，要判斷自己的隊長是誰，只能漫無目的的通過朋友的朋友關(guān)系問下去：“你是不是隊長？你是不是隊長？”這樣一來，隊長面子上掛不住了，而且效率太低，還有可能陷入無限循環(huán)中。于是隊長下令，重新組隊。隊內(nèi)所有人實行分等級制度，形成樹狀結(jié)構(gòu)，我隊長就是根節(jié)點，下面分別是二級隊員、三級隊員。每個人只要記住自己的上級是誰就行了。遇到判斷敵友的時候，只要一層層向上問，直到最高層，就可以在短時間內(nèi)確定隊長是誰了。由于我們關(guān)心的只是兩個人之間是否連通，至于他們是如何連通的，以及每個圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊長是誰，并不重要。所以我們可以放任隊長隨意重新組隊，只要不搞錯敵友關(guān)系就好了。于是，門派產(chǎn)生了。

http://i3.6.cn/cvbnm/6f/ec/f4/1e9cfcd3def64d26ed1a49d72c1f6db9.jpg

下面我們來看并查集的實現(xiàn)。 int pre[1000]; 這個數(shù)組，記錄了每個大俠的上級是誰。大俠們從1或者0開始編號（依據(jù)題意而定），pre[15]=3就表示15號大俠的上級是3號大俠。如果一個人的上級就是他自己，那說明他就是掌門人了，查找到此為止。也有孤家寡人自成一派的，比如歐陽鋒，那么他的上級就是他自己。每個人都只認自己的上級。比如胡青牛同學(xué)只知道自己的上級是楊左使。張無忌是誰？不認識！要想知道自己的掌門是誰，只能一級級查上去。 find這個函數(shù)就是找掌門用的，意義再清楚不過了（路徑壓縮算法先不論，后面再說）。

int find(int x)                                                                  //查找我（x）的掌門

{

    int r=x;                                                                       //委托 r 去找掌門

    while (pre[r ]!=r)                                                        //如果r的上級不是r自己（也就是說找到的大俠他不是掌門 = =）

    r=pre[r ] ;                                                                   // r 就接著找他的上級，直到找到掌門為止。

    return  r ;                                                                   //掌門駕到~~~

}

再來看看join函數(shù)，就是在兩個點之間連一條線，這樣一來，原先它們所在的兩個板塊的所有點就都可以互通了。這在圖上很好辦，畫條線就行了。但我們現(xiàn)在是用并查集來描述武林中的狀況的，一共只有一個pre[]數(shù)組，該如何實現(xiàn)呢？ 還是舉江湖的例子，假設(shè)現(xiàn)在武林中的形勢如圖所示。虛竹小和尚與周芷若MM是我非常喜歡的兩個人物，他們的終極boss分別是玄慈方丈和滅絕師太，那明顯就是兩個陣營了。我不希望他們互相打架，就對他倆說：“你們兩位拉拉勾，做好朋友吧。”他們看在我的面子上，同意了。這一同意可非同小可，整個少林和峨眉派的人就不能打架了。這么重大的變化，可如何實現(xiàn)呀，要改動多少地方？其實非常簡單，我對玄慈方丈說：“大師，麻煩你把你的上級改為滅絕師太吧。這樣一來，兩派原先的所有人員的終極boss都是師太，那還打個球??！反正我們關(guān)心的只是連通性，門派內(nèi)部的結(jié)構(gòu)不要緊的。”玄慈一聽肯定火大了：“我靠，憑什么是我變成她手下呀，怎么不反過來？我抗議！”抗議無效，上天安排的，最大。反正誰加入誰效果是一樣的，我就隨手指定了一個。這段函數(shù)的意思很明白了吧？

void join(int x,int y)                                                                   //我想讓虛竹和周芷若做朋友

{

    int fx=find(x),fy=find(y);                                                       //虛竹的老大是玄慈，芷若MM的老大是滅絕

    if(fx!=fy)                                                                               //玄慈和滅絕顯然不是同一個人

    pre[fx ]=fy;                                                                           //方丈只好委委屈屈地當了師太的手下啦

}

再來看看路徑壓縮算法。建立門派的過程是用join函數(shù)兩個人兩個人地連接起來的，誰當誰的手下完全隨機。最后的樹狀結(jié)構(gòu)會變成什么胎唇樣，我也完全無法預(yù)計，一字長蛇陣也有可能。這樣查找的效率就會比較低下。最理想的情況就是所有人的直接上級都是掌門，一共就兩級結(jié)構(gòu)，只要找一次就找到掌門了。哪怕不能完全做到，也最好盡量接近。這樣就產(chǎn)生了路徑壓縮算法。 設(shè)想這樣一個場景：兩個互不相識的大俠碰面了，想知道能不能揍。 于是趕緊打電話問自己的上級：“你是不是掌門？” 上級說：“我不是呀，我的上級是誰誰誰，你問問他看看?！?一路問下去，原來兩人的最終boss都是東廠曹公公。 “哎呀呀，原來是記己人，西禮西禮，在下三營六組白面葫蘆娃!” “幸會幸會，在下九營十八組仙子狗尾巴花！” 兩人高高興興地手拉手喝酒去了。 “等等等等，兩位同學(xué)請留步，還有事情沒完成呢！”我叫住他倆。 “哦，對了，還要做路徑壓縮?！眱扇诵盐?。 白面葫蘆娃打電話給他的上級六組長：“組長啊，我查過了，其習(xí)偶們的掌門是曹公公。不如偶們一起及接拜在曹公公手下吧，省得級別太低，以后查找掌門麻環(huán)。” “唔，有道理。” 白面葫蘆娃接著打電話給剛才拜訪過的三營長……仙子狗尾巴花也做了同樣的事情。 這樣，查詢中所有涉及到的人物都聚集在曹公公的直接領(lǐng)導(dǎo)下。每次查詢都做了優(yōu)化處理，所以整個門派樹的層數(shù)都會維持在比較低的水平上。路徑壓縮的代碼，看得懂很好，看不懂也沒關(guān)系，直接抄上用就行了?？傊鶎崿F(xiàn)的功能就是這么個意思。

http://i3.6.cn/cvbnm/60/98/92/745b3eac68181e4ee1fa8d1b8bca38bc.jpg

hdu1232

 1 #include<iostream> 2 using namespace std; 3 int  pre[1050]; 4 bool t[1050];               //t 用于標記獨立塊的根結(jié)點 5 int Find(int x) 6 { 7     int r=x; 8     while(r!=pre[r]) 9         r=pre[r];10     11     int i=x,j;12     while(pre[i]!=r)13     {14         j=pre[i];15         pre[i]=r;16         i=j;17     }18     return r;19 }20 void mix(int x,int y)21 {22     int fx=Find(x),fy=Find(y);23     if(fx!=fy)24     {25         pre[fy]=fx;26     }27 } 
28 int main()29 {30     int N,M,a,b,i,j,ans;31     while(scanf("%d%d",&N,&M)&&N)32     {33         for(i=1;i<=N;i++)          //初始化 34             pre[i]=i;35         36         for(i=1;i<=M;i++)          //吸收并整理數(shù)據(jù) 37         {38             scanf("%d%d",&a,&b);39             mix(a,b);40         }41         memset(t,0,sizeof(t));42         for(i=1;i<=N;i++)          //標記根結(jié)點43         {44             t[Find(i)]=1;45         }46         for(ans=0,i=1;i<=N;i++)47             if(t[i])48                 ans++;49                 50         printf("%d\n",ans-1);51         52     }53     return 0;54 }

//以下為原文附的代碼:
//回到開頭提出的問題，我的代碼如下：
#include <bits/stdc++.h>
using namespace std;
int pre[1000];
int find(int x)
{
    int r=x;
   while (pre[r ]!=r)
   r=pre[r ];
   int i=x; int j;
   while(i!=r)
   {
       j=pre[i ];
       pre[i ]=r;
       i=j;
   }
   return r;
}
int main()
{
   int n,m,p1,p2,i,total,f1,f2;
   while(scanf("%d",&n) && n)         //讀入n，如果n為0，結(jié)束
   {                                                    //剛開始的時候，有n個城鎮(zhèn)，一條路都沒有 //那么要修n-1條路才能把它們連起來
       total=n-1;
       //每個點互相獨立，自成一個集合，從1編號到n //所以每個點的上級都是自己
       for(i=1;i<=n;i++) { pre[i ]=i; }                //共有m條路
       scanf("%d",&m); 
       while(m--)
       { //下面這段代碼，其實就是join函數(shù)，只是稍作改動以適應(yīng)題目要求
           //每讀入一條路，看它的端點p1，p2是否已經(jīng)在一個連通分支里了
           scanf("%d %d",&p1,&p2);
           f1=find(p1);
           f2=find(p2);
               //如果是不連通的，那么把這兩個分支連起來
               //分支的總數(shù)就減少了1，還需建的路也就減了1
           if(f1!=f2)
            {
               pre[f2 ]=f1;
               total--;
            }
           //如果兩點已經(jīng)連通了，那么這條路只是在圖上增加了一個環(huán) //對連通性沒有任何影響，無視掉
      }
//最后輸出還要修的路條數(shù)
       printf("%d\n",total);
   }
   return 0;
}

關(guān)于動態(tài)連通性

我們看一張圖來了解一下什么是動態(tài)連通性：

假設(shè)我們輸入了一組整數(shù)對，即上圖中的(4, 3) (3, 8)等等，每對整數(shù)代表這兩個points/sites是連通的。那么隨著數(shù)據(jù)的不斷輸入，整個圖的連通性也會發(fā)生變化，從上圖中可以很清晰的發(fā)現(xiàn)這一點。同時，對于已經(jīng)處于連通狀態(tài)的points/sites，直接忽略，比如上圖中的(8, 9)。

動態(tài)連通性的應(yīng)用場景：

• 網(wǎng)絡(luò)連接判斷：

如果每個pair中的兩個整數(shù)分別代表一個網(wǎng)絡(luò)節(jié)點，那么該pair就是用來表示這兩個節(jié)點是需要連通的。那么為所有的pairs建立了動態(tài)連通圖后，就能夠盡可能少的減少布線的需要，因為已經(jīng)連通的兩個節(jié)點會被直接忽略掉。

• 變量名等同性(類似于指針的概念)：

在程序中，可以聲明多個引用來指向同一對象，這個時候就可以通過為程序中聲明的引用和實際對象建立動態(tài)連通圖來判斷哪些引用實際上是指向同一對象。

對問題建模：

在對問題進行建模的時候，我們應(yīng)該盡量想清楚需要解決的問題是什么。因為模型中選擇的數(shù)據(jù)結(jié)構(gòu)和算法顯然會根據(jù)問題的不同而不同，就動態(tài)連通性這個場景而言，我們需要解決的問題可能是：

• 給出兩個節(jié)點，判斷它們是否連通，如果連通，不需要給出具體的路徑

• 給出兩個節(jié)點，判斷它們是否連通，如果連通，需要給出具體的路徑

就上面兩種問題而言，雖然只有是否能夠給出具體路徑的區(qū)別，但是這個區(qū)別導(dǎo)致了選擇算法的不同，本文主要介紹的是第一種情況，即不需要給出具體路徑的Union-Find算法，而第二種情況可以使用基于DFS的算法。

建模思路：

最簡單而直觀的假設(shè)是，對于連通的所有節(jié)點，我們可以認為它們屬于一個組，因此不連通的節(jié)點必然就屬于不同的組。隨著Pair的輸入，我們需要首先判斷輸入的兩個節(jié)點是否連通。如何判斷呢？按照上面的假設(shè)，我們可以通過判斷它們屬于的組，然后看看這兩個組是否相同，如果相同，那么這兩個節(jié)點連通，反之不連通。為簡單起見，我們將所有的節(jié)點以整數(shù)表示，即對N個節(jié)點使用0到N-1的整數(shù)表示。而在處理輸入的Pair之前，每個節(jié)點必然都是孤立的，即他們分屬于不同的組，可以使用數(shù)組來表示這一層關(guān)系，數(shù)組的index是節(jié)點的整數(shù)表示，而相應(yīng)的值就是該節(jié)點的組號了。該數(shù)組可以初始化為：

即對于節(jié)點i，它的組號也是i。

初始化完畢之后，對該動態(tài)連通圖有幾種可能的操作：

• 查詢節(jié)點屬于的組

數(shù)組對應(yīng)位置的值即為組號

• 判斷兩個節(jié)點是否屬于同一個組

分別得到兩個節(jié)點的組號，然后判斷組號是否相等

• 連接兩個節(jié)點，使之屬于同一個組

分別得到兩個節(jié)點的組號，組號相同時操作結(jié)束，不同時，將其中的一個節(jié)點的組號換成另一個節(jié)點的組號

• 獲取組的數(shù)目

初始化為節(jié)點的數(shù)目，然后每次成功連接兩個節(jié)點之后，遞減1

API

我們可以設(shè)計相應(yīng)的API：

注意其中使用整數(shù)來表示節(jié)點，如果需要使用其他的數(shù)據(jù)類型表示節(jié)點，比如使用字符串，那么可以用哈希表來進行映射，即將String映射成這里需要的Integer類型。

分析以上的API，方法connected和union都依賴于find，connected對兩個參數(shù)調(diào)用兩次find方法，而union在真正執(zhí)行union之前也需要判斷是否連通，這又是兩次調(diào)用find方法。因此我們需要把find方法的實現(xiàn)設(shè)計的盡可能的高效。所以就有了下面的Quick-Find實現(xiàn)。

Quick-Find 算法：

 1 public class UF 2 { 3     private int[] id; // access to component id (site indexed) 4     private int count; // number of components 5     public UF(int N) 6     { 7         // Initialize component id array. 8         count = N; 9         id = new int[N];10         for (int i = 0; i < N; i++)11             id[i] = i;12     }13     public int count()14     { return count; }15     public boolean connected(int p, int q)16     { return find(p) == find(q); }17     public int find(int p)18     { return id[p]; }19     public void union(int p, int q)20     { 
21         // 獲得p和q的組號22         int pID = find(p);23         int qID = find(q);24         // 如果兩個組號相等，直接返回25         if (pID == qID) return;26         // 遍歷一次，改變組號使他們屬于一個組27         for (int i = 0; i < id.length; i++)28             if (id[i] == pID) id[i] = qID;29         count--;30     }31 }

舉個例子，比如輸入的Pair是(5， 9)，那么首先通過find方法發(fā)現(xiàn)它們的組號并不相同，然后在union的時候通過一次遍歷，將組號1都改成8。當然，由8改成1也是可以的，保證操作時都使用一種規(guī)則就行。

上述代碼的find方法十分高效，因為僅僅需要一次數(shù)組讀取操作就能夠找到該節(jié)點的組號，但是問題隨之而來，對于需要添加新路徑的情況，就涉及到對于組號的修改，因為并不能確定哪些節(jié)點的組號需要被修改，因此就必須對整個數(shù)組進行遍歷，找到需要修改的節(jié)點，逐一修改，這一下每次添加新路徑帶來的復(fù)雜度就是線性關(guān)系了，如果要添加的新路徑的數(shù)量是M，節(jié)點數(shù)量是N，那么最后的時間復(fù)雜度就是MN，顯然是一個平方階的復(fù)雜度，對于大規(guī)模的數(shù)據(jù)而言，平方階的算法是存在問題的，這種情況下，每次添加新路徑就是“牽一發(fā)而動全身”，想要解決這個問題，關(guān)鍵就是要提高union方法的效率，讓它不再需要遍歷整個數(shù)組。

Quick-Union 算法：

考慮一下，為什么以上的解法會造成“牽一發(fā)而動全身”？因為每個節(jié)點所屬的組號都是單獨記錄，各自為政的，沒有將它們以更好的方式組織起來，當涉及到修改的時候，除了逐一通知、修改，別無他法。所以現(xiàn)在的問題就變成了，如何將節(jié)點以更好的方式組織起來，組織的方式有很多種，但是最直觀的還是將組號相同的節(jié)點組織在一起，想想所學(xué)的數(shù)據(jù)結(jié)構(gòu)，什么樣子的數(shù)據(jù)結(jié)構(gòu)能夠?qū)⒁恍┕?jié)點給組織起來？常見的就是鏈表，圖，樹，什么的了。但是哪種結(jié)構(gòu)對于查找和修改的效率最高？毫無疑問是樹，因此考慮如何將節(jié)點和組的關(guān)系以樹的形式表現(xiàn)出來。

如果不改變底層數(shù)據(jù)結(jié)構(gòu)，即不改變使用數(shù)組的表示方法的話?？梢圆捎?span lang="en-us" xml:lang="en-us">parent-link的方式將節(jié)點組織起來，舉例而言，id[p]的值就是p節(jié)點的父節(jié)點的序號，如果p是樹根的話，id[p]的值就是p，因此最后經(jīng)過若干次查找，一個節(jié)點總是能夠找到它的根節(jié)點，即滿足id[root] = root的節(jié)點也就是組的根節(jié)點了，然后就可以使用根節(jié)點的序號來表示組號。所以在處理一個pair的時候，將首先找到pair中每一個節(jié)點的組號(即它們所在樹的根節(jié)點的序號)，如果屬于不同的組的話，就將其中一個根節(jié)點的父節(jié)點設(shè)置為另外一個根節(jié)點，相當于將一顆獨立的樹編程另一顆獨立的樹的子樹。直觀的過程如下圖所示。但是這個時候又引入了問題。

在實現(xiàn)上，和之前的Quick-Find只有find和union兩個方法有所不同：

 1 private int find(int p) 2 { 
 3     // 尋找p節(jié)點所在組的根節(jié)點，根節(jié)點具有性質(zhì)id[root] = root 4     while (p != id[p]) p = id[p]; 5     return p; 6 } 7 public void union(int p, int q) 8 { 
 9     // Give p and q the same root.10     int pRoot = find(p);11     int qRoot = find(q);12     if (pRoot == qRoot) 
13         return;14     id[pRoot] = qRoot;    // 將一顆樹(即一個組)變成另外一課樹(即一個組)的子樹15     count--;16 }

樹這種數(shù)據(jù)結(jié)構(gòu)容易出現(xiàn)極端情況，因為在建樹的過程中，樹的最終形態(tài)嚴重依賴于輸入數(shù)據(jù)本身的性質(zhì)，比如數(shù)據(jù)是否排序，是否隨機分布等等。比如在輸入數(shù)據(jù)是有序的情況下，構(gòu)造的BST會退化成一個鏈表。在我們這個問題中，也是會出現(xiàn)的極端情況的，如下圖所示。

為了克服這個問題，BST可以演變成為紅黑樹或者AVL樹等等。

然而，在我們考慮的這個應(yīng)用場景中，每對節(jié)點之間是不具備可比性的。因此需要想其它的辦法。在沒有什么思路的時候，多看看相應(yīng)的代碼可能會有一些啟發(fā)，考慮一下Quick-Union算法中的union方法實現(xiàn)：

 1 public void union(int p, int q) 2 { 
 3     // Give p and q the same root. 4     int pRoot = find(p); 5     int qRoot = find(q); 6     if (pRoot == qRoot) 
 7         return; 8     id[pRoot] = qRoot;  // 將一顆樹(即一個組)變成另外一課樹(即一個組)的子樹 9     count--;10 }

上面 id[pRoot] = qRoot 這行代碼看上去似乎不太對勁。因為這也屬于一種“硬編碼”，這樣實現(xiàn)是基于一個約定，即p所在的樹總是會被作為q所在樹的子樹，從而實現(xiàn)兩顆獨立的樹的融合。那么這樣的約定是不是總是合理的呢？顯然不是，比如p所在的樹的規(guī)模比q所在的樹的規(guī)模大的多時，p和q結(jié)合之后形成的樹就是十分不和諧的一頭輕一頭重的”畸形樹“了。

所以我們應(yīng)該考慮樹的大小，然后再來決定到底是調(diào)用：

id[pRoot] = qRoot 或者是 id[qRoot] = pRoot

即總是size小的樹作為子樹和size大的樹進行合并。這樣就能夠盡量的保持整棵樹的平衡。

所以現(xiàn)在的問題就變成了：樹的大小該如何確定？

我們回到最初的情形，即每個節(jié)點最一開始都是屬于一個獨立的組，通過下面的代碼進行初始化：

以此類推，在初始情況下，每個組的大小都是1，因為只含有一個節(jié)點，所以我們可以使用額外的一個數(shù)組來維護每個組的大小，對該數(shù)組的初始化也很直觀：

 而在進行合并的時候，會首先判斷待合并的兩棵樹的大小，然后按照上面圖中的思想進行合并，實現(xiàn)代碼：

 1 public void union(int p, int q) 2 { 3     int i = find(p); 4     int j = find(q); 5     if (i == j) return; 6     // 將小樹作為大樹的子樹 7     if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } 8     else { id[j] = i; sz[i] += sz[j]; } 9     count--;10 }

Quick-Union 和 Weighted Quick-Union 的比較：

可以發(fā)現(xiàn)，通過sz數(shù)組決定如何對兩棵樹進行合并之后，最后得到的樹的高度大幅度減小了。這是十分有意義的，因為在Quick-Union算法中的任何操作，都不可避免的需要調(diào)用find方法，而該方法的執(zhí)行效率依賴于樹的高度。樹的高度減小了，find方法的效率就增加了，從而也就增加了整個Quick-Union算法的效率。

上圖其實還可以給我們一些啟示，即對于Quick-Union算法而言，節(jié)點組織的理想情況應(yīng)該是一顆十分扁平的樹，所有的孩子節(jié)點應(yīng)該都在height為1的地方，即所有的孩子都直接連接到根節(jié)點。這樣的組織結(jié)構(gòu)能夠保證find操作的最高效率。

那么如何構(gòu)造這種理想結(jié)構(gòu)呢？

在find方法的執(zhí)行過程中，不是需要進行一個while循環(huán)找到根節(jié)點嘛？如果保存所有路過的中間節(jié)點到一個數(shù)組中，然后在while循環(huán)結(jié)束之后，將這些中間節(jié)點的父節(jié)點指向根節(jié)點，不就行了么？但是這個方法也有問題，因為find操作的頻繁性，會造成頻繁生成中間節(jié)點數(shù)組，相應(yīng)的分配銷毀的時間自然就上升了。那么有沒有更好的方法呢？還是有的，即將節(jié)點的父節(jié)點指向該節(jié)點的爺爺節(jié)點，這一點很巧妙，十分方便且有效，相當于在尋找根節(jié)點的同時，對路徑進行了壓縮，使整個樹結(jié)構(gòu)扁平化。相應(yīng)的實現(xiàn)如下，實際上只需要添加一行代碼：

 1     private int find(int p)  
 2     {  
 3         while (p != id[p])  
 4         {  
 5             // 將p節(jié)點的父節(jié)點設(shè)置為它的爺爺節(jié)點   6             id[p] = id[id[p]];  
 7             p = id[p];  
 8         }  
 9         return p;  
10     }

至此，動態(tài)連通性相關(guān)的Union-Find算法基本上就介紹完了，從容易想到的Quick-Find到相對復(fù)雜但是更加高效的Quick-Union，然后到對Quick-Union的幾項改進，讓我們的算法的效率不斷的提高。

這幾種算法的時間復(fù)雜度如下所示：

對大規(guī)模數(shù)據(jù)進行處理，使用平方階的算法是不合適的，比如簡單直觀的Quick-Find算法，通過發(fā)現(xiàn)問題的更多特點，找到合適的數(shù)據(jù)結(jié)構(gòu)，然后有針對性的進行改進，得到了Quick-Union算法及其多種改進算法，最終使得算法的復(fù)雜度降低到了近乎線性復(fù)雜度。

如果需要的功能不僅僅是檢測兩個節(jié)點是否連通，還需要在連通時得到具體的路徑，那么就需要用到別的算法了，比如DFS或者BFS。