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

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

typedef struct
{
    int length;           //節點自身的值
    node* head;         //指向表首的指針
    node* tail;           //指向表尾的指針，只有表頭節點對其賦值
    node* next;        //指向下一節點的指針
}node;
//對每個節點建立一個集合，需要O(1)時間
void MakeSet(node* u)
{
    u->head = u;
    u->tail = u;
    u->next = NULL;
    length = 1;
}
//查詢節點u所在集合的根節點，需要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）樹形結構
利用有根樹來表示集合，每棵樹表示一個集合，樹根即集合的根節點。

typedef struct
{
    Node* father;     //父節點指針
    int rank;          //樹深，用于啟發式合并
}node;
//對每個節點建立一個集合，需要O(1)時間
void MakeSet(node* u)
{
    u->father = u;
    rank = 1;
}
//查詢節點u所在集合的根節點，平均需要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）上述樹形結構的并查集也可以使用數組+索引的形式實現，在這里不再重復。
（2）樹結構下算法的耗時主要體現在Find函數上，可以通過路徑壓縮進行優化。例如，在對節點1執行Finds函數時，可以順便將節點1、2、3的父節點改為節點4，以后再對節點1、2、3調用Find函數時就只需要O(1)的時間。

//查詢節點u所在集合的根節點，時間復雜性******
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;
}