并查集，顧名思義是一種用來處理集合間合并與查詢的數(shù)據(jù)結(jié)構(gòu)，主要包括如下操作：
（1）查詢：查找元素所在的集合即根節(jié)點。
（2）合并：將兩個元素所在的集合合并為一個集合。
并查集主要用于圖論問題，例如判斷一個圖是否連通圖、某兩個點是否在圖中的同一連通子圖中等。算法需要以下幾個子過程：
（1）對每一個節(jié)點u建立一個集合MakeSet(u)，集合的元素只有u自己，表示最開始時u與其他節(jié)點沒有路徑。
（2）給出一個代表路徑的二元關(guān)系R（u，v），首先通過查詢功能Find()分別找到u和v所在集合的根節(jié)點，利用Find(a)==Find(b)判斷u和v是否在同一集合中，如果不是就使用合并功能Merge(a, b)將u所在的集合和v所在的集合合并。重復(fù)執(zhí)行該步。
（3）處理完所有二元關(guān)系后，每個集合便代表一個連通子圖。
接下來考慮選擇何種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)并查集，使算法的效率更高。

（1）單鏈表形式
同一集合中的節(jié)點串成一條鏈表，該鏈表的第一個節(jié)點所謂集合的根節(jié)點，具體的節(jié)點結(jié)構(gòu)如下：

typedef struct
{
    int length;           //節(jié)點自身的值
    node* head;         //指向表首的指針
    node* tail;           //指向表尾的指針，只有表頭節(jié)點對其賦值
    node* next;        //指向下一節(jié)點的指針
}node;
//對每個節(jié)點建立一個集合，需要O(1)時間
void MakeSet(node* u)
{
    u->head = u;
    u->tail = u;
    u->next = NULL;
    length = 1;
}
//查詢節(jié)點u所在集合的根節(jié)點，需要O(1)時間
node* Find(node* u)
{
    return u->head;
}
//將u和v所在的集合合并，需要O(N2)時間，N2是b所在集合鏈表長度
void Merge(node* a, node* b)
{
    node* p;

    a->head->tail->next = b->head;
    a->head->tail = b->head->tail;
    //將較短的表合并到較長表上
    if(a->head->length >= b->head->length)
    {
        p = b->head;
        while(p != NULL)
        {
            p->head = a->head;
            p = p->next;
        {
        a->head->length += b->head->length;
    }
    else
    {
        p = a->head;
        while(p != NULL)
        {
            p->head = b->head;
            p = p->next;
        {
        b->head->length += a->head->length;
    }
}

（2）樹形結(jié)構(gòu)
利用有根樹來表示集合，每棵樹表示一個集合，樹根即集合的根節(jié)點。

typedef struct
{
    Node* father;     //父節(jié)點指針
    int rank;          //樹深，用于啟發(fā)式合并
}node;
//對每個節(jié)點建立一個集合，需要O(1)時間
void MakeSet(node* u)
{
    u->father = u;
    rank = 1;
}
//查詢節(jié)點u所在集合的根節(jié)點，平均需要O(logN)時間，線性時最壞需要O(N)
node* Find(node* u)
{
    node* p;

    p = u;
    while(p->father != p)
    {
        p = p->father;
    }

    return p;
}
//將u和v所在的集合合并，需要O(1)時間
void Merge(node* a, node* b)
{
    node* p1, p2;

    p1 = Find(a);
    p2 = Find(b);
    if(p1->length >= p2->length)
    {
        p2->father = p1;
        if(p1->length == p2->length)
            p1->length += 1;
    }
    else if(p1->length < p2->length)
    {
        p1->father = p2;
    }
}

注意：
（1）上述樹形結(jié)構(gòu)的并查集也可以使用數(shù)組+索引的形式實現(xiàn)，在這里不再重復(fù)。
（2）樹結(jié)構(gòu)下算法的耗時主要體現(xiàn)在Find函數(shù)上，可以通過路徑壓縮進(jìn)行優(yōu)化。例如，在對節(jié)點1執(zhí)行Finds函數(shù)時，可以順便將節(jié)點1、2、3的父節(jié)點改為節(jié)點4，以后再對節(jié)點1、2、3調(diào)用Find函數(shù)時就只需要O(1)的時間。

//查詢節(jié)點u所在集合的根節(jié)點，時間復(fù)雜性******
node* Find(node* u)
{
    node* p, q;

    p = u;
    while(p->father != p)
    {
        p = p->father;
    }
    while(u != p)
    {
        q = u->father;
        u->father = p;
        u = q;
    }

    return p;
}