数据结构这书感觉和之前没读过一样……以前从来没发现树这章还讲了并查集……

若R是集合S上的一个等价关系，则由这个等价关系可以产生这个集合的唯一划分。

如何划分等价类

假设集合S有n个元素，m个形如(x, y)，的等价偶对(x, y都是集合S中的元素)。

(1)令S中每个元素各自形成一个只含单个成员的子集，记作S1, S2, ..., Sn。
(2)依次读入m个偶对，对每个读入的偶对(x, y)，判定x和y所属的集合，若他们还不属于同一集合，设x属于Si，y属于Sj，则合并Si和Sj。

集合操作的实现与并查集

其实上面描述的这种集合操作，归结起来有两个重要的：

Init(S)：令集合S中的每个元素x，单独称为一个集合Sx。

Find(x)：确定x属于那个子集合Si。

Merge(i, j)：合并子集合Si和Sj。

这些操作可以有很多实现方法，例如用位向量、有序表等。

此外，还可以使用并查集：

(1)将集合中的每个元素用结点表示，每个结点中含有一个指向其双亲的指针。
(2)约定根结点的成员做为子集合的类名。
根据上述规定，实现集合"并"(Merge)操作，只需要让一棵树的根指向另一棵即可。
而实现查找，就是依次向parent查找，直到到达该树的根。

下述是这种基础版本的并查集，其Find和Merge的时间复杂度分别为O(d)和O(1)，d是树的深度。

#include <stdio.h>

#define MAX 100
int parent[MAX];

void uf_init()
{
	int i;
	for(i=0;i<MAX;i++)
	{
		parent[i] = i;
	}
}

void uf_union(int i, int j)
{
	if(i<0 || i>=MAX || j<0 || j>=MAX)
	{
		return ;
	}
	int px = uf_find(i);
        int py = uf_find(j);
        parent[px] = py;
}

int uf_find(int x)
{
	if(x<0||x>=MAX)
	{
		return -1;
	}
	if(parent[x]==x)
	{
		return parent[x];
	}else
	{
		return uf_find(parent[x]);
	}
}

int main()
{
	int i;
	uf_init();
	uf_union(0, 1);
	for(i=0;i<10;i++)
	{
		printf("%d\n", uf_find(i));
	}
	return 0;
}

并查集优化

(1)rank，秩的压缩，即总是把含孩子少的合并到孩子多的子树上。以减少不平衡树的产生。但是话说这个优化感觉有限。

(2)路径压缩。实际是记忆搜索的变种。如下：

int uf_find(int x)
{
	if(x<0||x>=MAX)
	{
		return -1;
	}
	if(parent[x]==x)
	{
		return parent[x];
	}else
	{
		return uf_find(parent[x]);
	}
}

上述优化后，查找和合并的时间复杂度都可以认为是常数级别。