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

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

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

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

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

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

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

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

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

在實現(xiàn)的時候送上一道經(jīng)典的例題和解法，需要注意的是在解題當中如何初始化pre數(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é)束
   {                                                    //剛開始的時候，有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ù)，只是稍作改動以適應題目要求
           //每讀入一條路，看它的端點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;
}

在對并查集進行了學習后，不妨拿出一道例題，進行深一步的利用：

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

之所以將時間由大到小排序后再進行判斷，是為了解決以下問題：
1、可能有兩座橋是在同一天壞的且壞掉后都會進行抗議，那么為了統(tǒng)計重復的天數(shù)還要另外開辟數(shù)組且每次都要遍歷查重。
2、如果是從時間由小到大排的，那么需要解決的問題是：首先從第一座要壞的橋開始，初始化所有的橋，建立一棵或多棵樹，然后從第一座橋開始判斷，是否兩個小島連通。需要注意的是，該樹的生成已經(jīng)是在加入了該座橋的情況下產(chǎ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é)點  
{  
    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;//表示前一次是在第幾天進行反抗的  
        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;  
}