并查集詳解

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

來看一個執行個體，​​杭電1232暢通工程​​

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

以下面這組資料輸入資料來說明

4 2 1 3 4 3

第一行告訴你，一共有4個點，2條路。下面兩行告訴你，1、3之間有條路，4、3之間有條路。那麼整幅圖就被分成了1-3-4和2兩部分。隻要再加一條路，把2和其他任意一個點連起來，暢通工程就實作了，那麼這個這組資料的輸出結果就是1。好了，現在程式設計實作這個功能吧，城鎮有幾百個，路有不知道多少條，而且可能有回路。 這可如何是好？

我以前也不會呀，自從用了并查集之後，嗨，效果還真好！我們全家都用它！

并查集由一個整數型的數組和兩個函數構成。數組pre[]記錄了每個點的前導點是什麼，函數find是查找，join是合并。

int pre[1000 ];

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

{ 

    int r=x;

    while ( pre[r ] != r )                                                                                              //傳回根節點 r

          r=pre[r ];

    int i=x , j ;

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

    {

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

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

         i=j;

    }

    return r ;

}

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

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

{

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

    if(fx!=fy)

        pre[fx ]=fy;

}

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

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

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

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

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

{

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

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

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

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

}

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

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

{

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

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

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