并查集实现

并查集意思就是合并，判断两个元素是否在一个集合内，因为树中结点只能有一个父亲，所以可以用数组father[ i ]来表示树中结点和父亲的关系，i代表某结点，father[ i ]代表i的父亲结点，i == 2 , father[ i ] == 1 ，则说明结点2的父亲是1。

判断两个集合是不是同一个集合，只用判断其根节点是否相同即可，因为对同一个集合来说只存在一个根节点，且将其作为所属集合的标识。

查找

void findFather(int x){
	if(x == father[x]){
		return x;//找到根节点； 
	}else {
		findFather(father(x) );//向上递归,知道找到根节点; 
	} 
} 

合并:

void Union(int a, int b){
	int faA = findFather( a );
	int faB = findFather( b );
	if(faA != faB){
		father[faA] = faB;//让其中一个根结点指向另外一个结合的根结点即可合并这两个集合； 
	}
}

并查集的性质：在合并的过程中，只对两个不同的集合进行合并，如果两个元素在相同集合内，不做操作，这样可以保证集合内不会产生环。

  路径压缩：
        因为如果集合出现了链状，查找起来时间复杂度就很大，因此可以进行查找优化，即将查找x路径上的父节点包括第一次输入的x全部指向根节点，这样就像一朵花一样，查询的时间复杂度只有o(1)，这样的方法叫做路径压缩。

代码：

int findFather(int x){
	if(x == father[x]){
		return x//输入的x就是根节点； 
	}else {
		int f = findFather(father[x]);//递归找到根节点; 
		father[x] = f;//回溯将路径上的父亲节点全部指向根节点;
		return f;  
	}
} 

好朋友（并查集的例题）
Description
有一个叫做“数码世界”奇异空间，在数码世界里生活着许许多多的数码宝贝，其中有些数码宝贝之间可能是好朋友，并且数码宝贝世界有两条不成文的规定：
第一，数码宝贝A和数码宝贝B是好朋友等价于数码宝贝B与数码宝贝A是好朋友
第二，如果数码宝贝A和数码宝贝C是好朋友，而数码宝贝B和数码宝贝C也是好朋友，那么A和B也是好朋友

现在给出这些数码宝贝中所有好朋友的信息问：可以把这些数码宝贝分成多少组，满足每组中的任意两个数码宝贝都是好朋友，而且任意两组之间的数码宝贝都不是好朋友

Input
输入的第一行有两个正整数n(n <= 100)和m(m <= 100)，分别表示数码宝贝的个数和好朋友的组数，其中数码宝贝编号为1~n。

Output
输出一个整数，表示这些数码宝贝可以分成的组数

Sample Input

4 2
1 4
2 3

Sample Output

2

 Sample Input

7 5
1 2
2 3
3 1
1 4
5 6

Sample Output

3

思路：

有直接或者间接关系的放在一个集合用并查集，区分集合是用结合的根结点是相同，同一个结合内的元素根节点相同。

一组朋友如果两个的根结点都不相同说明不在一个集合内（查），但是又因为两个朋友间有连接关系，因此要将其放到一个集合内（并），因为一个根节点一个集合，用一个hashtable标识根结点，后期再数根节点的个数就知道集合的个数了，即分出的小组个数。

代码：
 

#include
using namespace std;
const int maxn = 110;
bool isroot[maxn] = {false};
int father[maxn] = {0};
int n,m,a,b,rootnum=0;
void ini(int n){
	for(int i=1;i<=n;i++){
		father[i] = i;//初始化，保证根结点指向自己; 
	}
}
 
int findFather(int x){//递归求结点的根节点; 
	if(father[x] == x) return x;
	else {
		int f=findFather(father[x]);//往上递归，找到根节点，f是根结点;
		father[x] == f;//让路径上的结点全部指向根节点，优化查找;
		return f;//返回根节点给上一层结点的f赋值，将根节点的值传下去; 
	}
}
 
void Union(int a, int b){
	int fa=findFather(a);
	int fb=findFather(b);
	if(fa != fb){//说明是不同的集合，不同的集合并起来; 
		father[fb] = fa;//b所在集合指向a所在集合； 
	}
}
 
int main ( ){
	scanf("%d %d",&n,&m);//输入n个数码宝贝和m组数码宝贝朋友关系；
	ini(n);
	for(int i=0;i
		scanf("%d %d",&a,&b);
		Union(a, b);
	}
	for(int i=1;i<=n;i++) isroot[findFather(i)] = true;//保证只有一个结点的集合也算做一个集合； 
	for(int i=1;i<=n;i++) rootnum += isroot[i];
	printf("%d",rootnum);//根结点的个数就是集合的个数; 
}