数据结构之——并查集

    用于不相交集合的数据结构——并查集。每个集合通过一个代表来识别，设x表示一个对象，我们希望支持一下操作：

    MakeSet(x)：建立一个新的集合，其唯一成员就是x。

    Union(x,y)：将包含x和y的动态集合（比如说Sx和Sy）合并为一个新的集合。

    FindSet(x)：返回一个指针，指向x对象所属集合的代表(唯一)。

    一种加权合并的启发式策略。

    第一种启发：按秩合并(Union by rank)，其思想是使包含较少结点的树根指向包含结点较多的树根。

    第二种启发：路径压缩(path compression)，它非常简单而有效，路径压缩不改变结点的秩。

    当联合使用这两种策略时，最坏时间复杂度为O(4*m)。m为执行Union、findSet的次数，与对象个数n无关。

 

POJ1611：

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

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

#include <iostream>
const int MAX = 30001;
int n,m;
int p[MAX],rank[MAX];
int num[MAX];			//集合元素个数

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

void Union(int x,int 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[y]++;
		num[y] +=num[x];
	}
}

int main()
{
	int i,j,k;
	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 = findSet(a);
				s2 = findSet(b);
				Union(s1,s2);
				a = i;
			}
		}
		i = findSet(0);
		printf("%d\n",num[i]);
	}
	return 0;
}

 

POJ1703,2924

    城市里面有两种帮派，警察想知道某两个人是否属于一个帮派。条件：给出a和b属于不同的帮派。

    用一个一维数组e[]保存敌对关系，例如e[a]=b，表示a的敌人是b，则在合并时：a与e[b]合并,b与e[a]合并。意思是a与b的敌人(a的朋友)合并。

#include <iostream>
const int MAX = 100001;
int p[MAX],rank[MAX],e[MAX];
//e[a] = b 表示a的敌人是b
int findSet(int x)
{
	if(p[x] != x)
		p[x] = findSet(p[x]);
	return p[x];
}

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

void initial(int n)
{
	for(int i = 1; i <= n; i++)
	{
		p[i] = i;
		rank[i] = 0;
		e[i] = 0;
	}
}

int main()
{
	int i,j;
	int cases;
	int n,m;
	char c;
	int a,b;
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%d %d",&n,&m);
		initial(n);
		for(i = 1; i <= m; i++)
		{
			getchar();
			scanf("%c %d %d",&c,&a,&b);
			if(c == 'A')
			{
				int fa = findSet(a);
				int fb = findSet(b);
				if(fa == fb)
					printf("In the same gang.\n");
				else
				{
					fb = findSet(e[b]);
					if(fa == fb)
						printf("In different gangs.\n");
					else
						printf("Not sure yet.\n");
				}
			}
			else //输入：a和b是敌人
			{
				int e1 = e[b];
				int e2 = e[a];
				if(e1 == 0)
					e[b] = a;
				else
					Union(a,e1);	//将a和b的敌人(即a的朋友)合并
				if(e2 == 0)
					e[a] = b;
				else
					Union(b,e2);	//将b和a的敌人(即b的朋友)合并
			}
		}
	}
	return 0;
}

 

POJ1182

    待续。。