poj 1611

   定义：并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，并就是按一定顺序将属于同一组的元素所在的集合合并。

l         并查集的精髓（即它的三种操作，结合实现代码模板进行理解）：

1、Make_Set(x) 把每一个元素初始化为一个集合

初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身（也可以根据情况而变）。

2、Find_Set(x) 查找一个元素所在的集合

查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并的最终依据。
判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。
合并两个集合，也是使一个集合的祖先成为另一个集合的祖先，具体见示意图

3、Union(x,y) 合并x,y所在的两个集合

合并两个不相交集合操作很简单：利用Find_Set找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。如图

 

 

l         并查集的优化

1、Find_Set(x)时 路径压缩
寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find_Set(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？
答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find_Set(x)时复杂度就变成O(1)了，如下图所示；可见，路径压缩方便了以后的查找。

 

2、Union(x,y)时 按秩合并
即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。

 

主要代码实现：

int Find_Set(int x)
{
	if (x!=p[x])
		p[x]=Find_Set(p[x]);
	return p[x];
}

void Union(int x,int y)
{
	x=Find_Set(x);
	y=Find_Set(y);
	if(x==y)
		return;
	if (rank[x]>rank[y])
	{
		p[y]=x;
		num[x]+=num[y];
	} 
	else
	{
		p[x]=y;
		if (rank[x]=rank[y])
			rank[x]++;
		num[y]+=num[x];
	}
}

 

 

 

 

 

 

 

 

 

POJ1611：

题目大意：SARS(非典型肺炎)传播得非常厉害，其中最有效的办法是隔离那些患病、和患病者接触的人。现在有几个学习小组，每小组有几个学生，一个学生可能会参加多个小组。小组中只要有一个人得病，其余的都是嫌疑人。现在已知这些小组的人员，且0号学生已经患病，求一共有多少个嫌疑人。

分析：每个小组的人员属于同一个集合。在根节点记录每个集合的个数num[i]，然后找到0所属的根节点，num[findSet(0)]即为所有的嫌疑人数。

#include <iostream>
const int Max=30001;

int p[Max],rank[Max];
int num[Max];//元素个数

int Find_Set(int x)
{
	if (x!=p[x])
		p[x]=Find_Set(p[x]);
	return p[x];
}

void Union(int x,int y)
{
	x=Find_Set(x);
	y=Find_Set(y);
	if(x==y)
		return;
	if (rank[x]>rank[y])
	{
		p[y]=x;
		num[x]+=num[y];
	} 
	else
	{
		p[x]=y;
		if (rank[x]=rank[y])
			rank[x]++;
		num[y]+=num[x];
	}
}

int main()
{
	int i,j,k,n,m;
	int a,b;
	int s1,s2;
	while (true)
	{
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)
			break;
		for (i=0;i<n;i++)
		{
			p[i]=i;
			rank[i]=0;
			num[i]=1;
		}
		for (i=0;i<m;i++)
		{
			scanf("%d",&k);
			scanf("%d",&a);
			for (j=1;j<k;j++)
			{
				scanf("%d",&b);
				s1=Find_Set(a);
				s2=Find_Set(b);
				Union(s1,s2);
				/*a=i;*/			
			}
		}
		i=Find_Set(0);
		printf("%d",num[i]);
	}
	return 0;
}