并查集-UnionFind

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

Union-Find算法有两个操作

Find操作：

确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

Union操作：

将两个子集合并成同一个集合。

1、Union-Find简单实现

对于一个数组a[N], 用一个辅助数组id[N]表示数组a中每一个元素所属的集合，如果a[i]和a[j]属于同一个集合，那么id[i] = id[j].

//返回元素x所属集合
int find(int a[N], int id[N], int x)
{
	for(int i=0; i<N; i++)
		if(a[i]==x)
			return id[i]
}
//判断两个元素是否属于同一集合
int sameSet(int id[N], int p, int q)
{
	return id[p]==id[q];
}
//合并第p个和第q个元素所属集合
void union(int id[N], int p, int q)
{
	int pid = id[p];
	for(int i=0; i<N; i++)
		if(id[i]==id[q])
			id[i]=pid;
}

2、方法1在union操作时太慢，对每一个集合设置一个root，合并时，只需把一个集合的root作为另一个集合的子节点挂上去。但是这样会生成一棵很高的不平衡的树，导致向上搜索root时时间复杂度太高，加入路径压缩技术(path compression).

//将id数组改成parent数组更形象，返回一个元素所属集合
int root(int parent[N], int i)
{
	while(i!=parent[i])
	{
		parent[i] = parent[parent[i]];//路径压缩
		i = parent[i];
	}
	return i;
}
int sameSet(int parent[N], int p, int q)
{
	return root(parent,p)==root(parent, q);
}

void union(int parent[N], int p, int q)
{
	int proot = root(parent, p);
	int qroot = root(parent, q);
	parent[qroot] = proot;
}

（推荐一个普林斯顿大学的UnionFind算法教程）