使用C语言实现并查集

1.集合

数学中集合的定义：具有某种特定性质的具体的或抽象的对象汇总而成的集体。其中，构成集合的这些对象则称为该集合的元素

集合比如：一个班级的同学；一个生物群落，同样爱好的人等。但是这些集合中之间是不相交的，也就是不属于同一个集合（当然这些大家都明白，只是因为接下来的内容需要，所以提及这个概念）。

 （1）多个集合

 怎么判断集合a中的元素d是属于集合a的呢?

思路：其实集合中的元素组成的就像一棵树一样，既然是树的话，那么就有一个“根”节点，如果从d->b->a找到a这个根节点的话，就可以判断元素d是否属于集合a了。

怎么合并两个集合呢？

思路：只要集合b中的根节点e的父节点改为节点a即可，也就是让一个集合的根节点是另一个结合的根节点。

 （2）代码的实现

根据上面提到的查找某个节点和合并两个集合的思路，实现其代码：

注：由于a节点没有父节点，所以将parent设置为-1，其他的节点同样将父节点都设置为数组下标，比如b节点的父节点为a,而a的数组下标为0.

#include<stdio.h>
#include<stdlib.h>
 
#define maxn 100
 
typedef int ElemType;
 
int parent[maxn];
 
//初始化
void InitParent(int n){
	for(int i=0;i<n;i++){
		parent[i]=-1;
	}
} 
 
//查找某个节点从属的集合
int find(int x){
	while(parent[x]>=0){
		x=parent[x];
	}
	return x;
} 
//合并两个集合
void Union(int root1,int root2){
	if(root1==root2){
		return;
	}
	parent[root2]=root1;
} 

（3）合并操作的优化

可是上面存在一个缺点就是，就是在合并的时候，查找的操作find的时间复杂度最坏的情况下为O(n)，并且将n个元素进行多次的合并时间复杂度可能达到O(n^2),看下图：

 

 注：可以看到两种合并方式导致树的高度不同，如果树增高太多的话，那么会导致后面查找的时候更加的耗时，为了尽量减小合并之后树的高度，应该将较矮的树合并到较高的树中，这样树的高度不至于太高。

优化之后的合并代码：使用根节点的绝对值表示树的节点数：

a和e对应的parent=-4，表示| parent |=4为树的节点数。

//合并两个集合
void Union_1(int root1,int root2){
	if(root1==root2){
		return;
	}
	if(abs(parent[root2])<abs(parent[root1])){
		parent[root1]+=parent[root2];
		parent[root2]=root1;
	}else{
		parent[root2]+=parent[root1];
		parent[root1]=root2;
	}
}  

注：改进之后的find查找时间复杂度最坏为O(log2n)，将n个独立的元素为一个集合的合并操作最坏的时间复杂度为O(nlog2n).

（4）查找操作的优化

采用路径压缩的方式进行优化：首先找到根节点，再将查找根节点路径上所经过的所有节点都挂到根节点上，这样在查找根节点的时候更少的经过中间的路径，如下图所示：

 

这样在查找节点b,d的时候可以直接查找到根节点e了。

//查找某个节点从属的集合
int find_1(int x){
	int root=x;
	//首先找到根节点 
	while(parent[x]>=0){
		root=parent[root];
	}
	//如果x不能直接找到根节点，那么需要对其经过路径上的
	//所有节点直接指向根节点进行路径的压缩 
	if(x!=root){
		int t=parent[x];
		parent[t]=root;
		x=t; 
	}
	return root;
} 

注：改进之后的find查找时间复杂度为O(a(n))，将n个独立的元素为一个集合的合并操作的时间复杂度为O(n*a(n)).

PTA团体程序设计天梯赛-L2-024 部落

poj1703

poj2524

poj1182

HDU1213

HDU1232