背景：如果我们需要将元素划分到若干不相交的子集中，使用并查集可以快速确定某两个元素是否位于同一个子集。

并查集是一种数据结构，除了Union-Find Set，又叫做Disjoint-Set。更确切的说，它主要包含了两种操作：Find和Union。具体信息可以见维基百科：《Disjoint-set data structure 》

并查集主要包含两个操作：

Find(x)：返回元素位于那个划分的子集合内。

Union(x, y)：将x, y两个集合中的元素合并为一个集合。

其实还有一个操作，Make_Set(x)：初始化x元素，让他属于独立的集合（它子集）。

并查集的最子出思想：为每一个集合x创建一个链表，链表的表头被选为“代表元”(root)。代表元的parent指向子集，而链表的其他元素直接或间接指向root(间接是由union操作导致的)。

因此，查找的时候，我们将递归查找，直到到达代表元root。

下面是一个最naive版本的并查集实现：

#include <stdio.h>

#define MAX 100

int data[MAX];
int parent[MAX]; // store each elem's represent.. elem..

void make_set(int x)
{
	parent[x] = x;
}

int find_set(int x)
{
	if(parent[x]==x)
	{
		return x;
	}else
	{
		return find_set(parent[x]);
	}
}

// Union x to y
int union_set(int x, int y)
{
	int parent_x = find_set(x);
	int parent_y = find_set(y);
	parent[parent_x] = parent_y;
}

int main()
{
	// Make individual set 0~5
	int i = 0;
	for(i=0;i<5;i++)
	{
		make_set(i);
	}
	// Print Elem's belong to union
	for(i=0;i<5;i++)
	{
		printf("%d : %d\n",i, find_set(i));
	}
	printf("\n\n");
	// Union 1~3 to i+1(final 4)
	for(i=1;i<4;i++)
	{
		union_set(i, i+1);
	}
	// Print Elem's belong to union
	for(i=0;i<5;i++)
	{
		printf("%d : %d\n",i, find_set(i));
	}
}

上述naive的Find的时间复杂度是O(logn)，合并的复杂度是O(1)。

上述并查集的实现有很多可以优化的空间。

最简单的是路径压缩（Path Compression）。实际上，在Find是一个递归的过程，而这之中很多结点的parent都是被多次、反复查找过的，我们可以用类似记忆化搜索的方法，“缓存”这些parent，让他们在计算过一次后，直接指向最终的“代表元”。这样，Find的实践复杂度会下降为O(a(n))，其中a(n)是Ackermann的反函数。对于大部分可以观察到的n，其值都是5以内。所以时间复杂度非常低！

int find_set(int x)
{
    if(parent[x]!=x)
    {
        parent[x] = find_set(parent[x]);
    }
    return parent[x];
}

另外一个优化是秩合并(Union by rank)。这主要是为了解决合并的平衡问题。即，我们总是应该把较小(层少)的数合并到大的树上。

为此，我们给每个元素加上一个秩rank，代码如下：

void make_set(int x)
{
    parent[x] = x;
    rank[x] = 0;
}

// Union x to y
int union_set(int x, int y)
{
    int parent_x = find_set(x);
    int parent_y = find_set(y);
    if(x==y)
    {
        return;
    }
    // Append set of small rank to big
    if(rank[x]<rank[y])
    {
        parent[parent_x] = parent_y;
    } else if(rank[x]>rank[y])
    {
        parent[parent_y] = parent_x;
    } else
    {
        parent[parent_x] = parent_y;
        rank[parent_y]++;
    }
}