用途

主要用于解決判斷兩結(jié)點是否能連通之類的問題。
　　
思想

建立并查集數(shù)組set[]，初始化全部置-1。set[b]=a代表結(jié)點b的父結(jié)點為a。判斷兩結(jié)點是否連通，只要依次找到兩結(jié)點的根結(jié)點并判斷是否相同即可。若不同，將一結(jié)點的根節(jié)點連接作為另一節(jié)點根節(jié)點的子樹，即可完成連通操作。

/*尋根*/
int findRoot(int x)
{
    while(set[x]!=-1)
        x=set[x];
    return x;
}

/*連通操作*/
void Union(int a,int b)
{
    set[findRoot(b)]=findRoot(a);
}

注意
?
　　用以上方法操作時，一旦數(shù)據(jù)過多，往往會造成運行超時的結(jié)果，原因在于并查集樹過高，搜索根節(jié)點時間長。下面提供兩種解決思路：
　　
1.路徑壓縮
　　變更set[i]值的含義，將set[i]直接指向包含結(jié)點i的樹的根節(jié)點，使每次查找根節(jié)點所需時間大大減少。具體做法為：每一次尋根的時候，變更set[i]值為根節(jié)點。經(jīng)過路徑壓縮后效率可以達到O(N)。

/*路徑壓縮*/
int findRoot(int x)
{
    /*注意x即為根節(jié)點的情況，此時直接返回x即可*/
    if(set[x]==-1)
        return x;
    else
    {
        int temp=x;     //先將x的值保存下來
        while(set[x]!=-1)
            x=set[x];
        set[temp]=x;    //更新set[]
        return x;
    }
}

2.按秩歸并
　　壓縮路徑存在的一個問題是會破壞樹的形狀，這是可以考慮使用按秩歸并的方法。
　　對于兩顆高度不一的樹，若將高樹并到矮樹上，則得到的樹高度為原高樹高度加一，為了不使樹一直增高，我們采取的做法是每一次合并都將矮樹合并到高樹上（通過根節(jié)點的值來記錄樹高，即set[root]=-樹高）。當然也可以從樹的規(guī)模入手，將小樹歸并到大樹上。
　　最壞情況下樹高O(logN)，按秩歸并的復雜度可以低至O(NlogN)。

/*比高度，set[root]存儲高度*/
void Union(int a,int b)
{
    int aRoot=findRoot(a);
    int bRoot=findRoot(b);
    if(set[aRoot]<set[bRoot])       //若a為高樹
        set[bRoot]=aRoot;
    else        
    {
        if(set[aRoot]==set[bRoot])  //若樹高相等
            --set[bRoot];    //合并后樹高要加一
        set[aRoot]=bRoot;
    }
}

/*比規(guī)模，set[root]存儲規(guī)模*/
void Union(int a,int b)
{
    int aRoot=findRoot(a);
    int bRoot=findRoot(b);
    if(set[aRoot]<set[bRoot])   //a規(guī)模大于b
    {
        set[aRoot]+=set[bRoot];//注意規(guī)模要合并
        set[bRoot]=aRoot;
    }
    else
    {
        set[bRoot]+=set[aRoot];
        set[aRoot]=bRoot;
    }
}

3.以上兩種方法相結(jié)合，可以實現(xiàn)-1s，非常暴力。