最近看了一篇頗有趣的并查集文章，放在這里推薦一下，順便自己也想總結(jié)一下。
http://blog.csdn.net/dellaserss/article/details/7724401/
并查集：
判斷圖是否連通，以及有幾個(gè)連通分量。
其實(shí)現(xiàn)方法，卻是用樹來進(jìn)行查找。

原理：
把每一個(gè)連通分量都看做一個(gè)樹，判斷兩個(gè)結(jié)點(diǎn)是否在一個(gè)連通分量中（即是否屬于一棵樹），需要查找是否有同一個(gè)根節(jié)點(diǎn)，如果是，則是同一個(gè)連通分量，不是，則不是同一個(gè)連通分量。

實(shí)現(xiàn)方法：
每一個(gè)結(jié)點(diǎn)都記錄其雙親結(jié)點(diǎn)，雙親結(jié)點(diǎn)再記錄自己的雙親結(jié)點(diǎn)，直到根節(jié)點(diǎn)，其記錄的雙親結(jié)點(diǎn)是自己的下標(biāo)。

int find(int x)
{
    int r=x;
    while (pre[r ]!=r) 
    r=pre[r ] ;    
    return  r ; }

初始化方案：
可以把每一個(gè)結(jié)點(diǎn)的pre值都記錄為自己，每當(dāng)出現(xiàn)一條邊，如果兩個(gè)結(jié)點(diǎn)屬于不同的連通分量，邊的一個(gè)結(jié)點(diǎn)的根節(jié)點(diǎn)就等于另一個(gè)結(jié)點(diǎn)的根節(jié)點(diǎn)，如果覺得不容易理解，看圖解：

最后結(jié)合成的兩種樹都是正確的合并方式，可以根據(jù)自己的意愿結(jié)合。

void join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)    
    pre[fx ]=fy;      
}

優(yōu)化：
每次判斷兩個(gè)結(jié)點(diǎn)是否是同一個(gè)聯(lián)通分量都需要從該結(jié)點(diǎn)開始迭代到根節(jié)點(diǎn)，為了節(jié)省時(shí)間復(fù)雜度，可以讓每一個(gè)結(jié)點(diǎn)都記錄所在樹的根節(jié)點(diǎn)，當(dāng)出現(xiàn)樹的合并時(shí)，每向上迭代尋找一次雙親結(jié)點(diǎn)就重新賦值一次：

r=find(x);
int i=x,j;  
    while(pre[i]!=r)  
    {  
        j=pre[i];  
        pre[i]=r;  
        i=j;  
    }  

在實(shí)現(xiàn)的時(shí)候送上一道經(jīng)典的例題和解法，需要注意的是在解題當(dāng)中如何初始化pre數(shù)組和對(duì)數(shù)組的賦值過程原理。

實(shí)現(xiàn)：

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

在對(duì)并查集進(jìn)行了學(xué)習(xí)后，不妨拿出一道例題，進(jìn)行深一步的利用：

分析題意：
題目所給定的是兩個(gè)小島在有一天突然由連通變成不連通的時(shí)候進(jìn)行抗議一天，求解共抗議多少天。
逆序思維：
將時(shí)間從大到小排序，可以知道小島從開始的不連通漸漸連通，而我們要求得是在加上一座橋的時(shí)候兩個(gè)小島從連通到不連通的數(shù)量。
故在加入一座橋時(shí)可以分為兩種情況：
1、判斷兩個(gè)小島是否連通，如果是，那么加上橋以后還連通，所以該橋毀掉后居民不會(huì)抗議。
2、如果不連通，那么在這天居民將會(huì)舉行游行，游行天數(shù)加一。

之所以將時(shí)間由大到小排序后再進(jìn)行判斷，是為了解決以下問題：
1、可能有兩座橋是在同一天壞的且壞掉后都會(huì)進(jìn)行抗議，那么為了統(tǒng)計(jì)重復(fù)的天數(shù)還要另外開辟數(shù)組且每次都要遍歷查重。
2、如果是從時(shí)間由小到大排的，那么需要解決的問題是：首先從第一座要壞的橋開始，初始化所有的橋，建立一棵或多棵樹，然后從第一座橋開始判斷，是否兩個(gè)小島連通。需要注意的是，該樹的生成已經(jīng)是在加入了該座橋的情況下產(chǎn)生的，可以參考之前的圖片：

想要知道是否加上該座橋后連通，需要做的只能是在不建立這座橋之前進(jìn)行建樹，而按照從小到大排序建樹的規(guī)則是不允許做到的，所以只有按照從大到小排序建樹。

在理解到這里的情況下，就可以編碼解決問題了：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
  
using namespace std;  
  
struct node  
{  
    int x,y,d;  
} s[100000+5];  
int n,f[10000+5];  
  
bool cmp(node a,node b)  
{  
    return a.d>b.d;  
}  
  
void Set()  
{  
    for (int i=1; i<=n; i++)  
        f[i]=i;  
}  
  
int Find(int x)//查找根節(jié)點(diǎn)  
{  
    if (f[x]==x)  
        return x;  
    return f[x]=Find(f[x]);  
}  
  
bool Union(int x,int y)  
{  
    x=Find(x);  
    y=Find(y);  
    if (x!=y)  
    {  
        f[x]=y;  
        return 1;  
    }  
    return 0;  
}  
  
  
int main()  
{  
    int m;  
    while (~scanf("%d%d",&n,&m))  
    {  
        for (int i=1; i<=m; i++)  
        {  
            scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].d);  
        }  
        sort(s+1,s+m+1,cmp);  
        Set();  
        int pre=-1,ans=0;//表示前一次是在第幾天進(jìn)行反抗的  
        for (int i=1; i<=m; i++)  
        {  
            int way=Union(s[i].x,s[i].y);//way=0表示之前有橋，不需要在建橋  
            if (way==1&&s[i].d!=pre)  
            {  
                ans++;  
                pre=s[i].d;  
            }  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}