并查集，顾名思义是一种用来处理集合间合并与查询的数据结构，主要包括如下操作：
（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;
}