poj 2524 并查集.txt

ACM资料大集合

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define NMAX 50010
//POJ 2524 并查集
int fa[NMAX];
int rel[NMAX];
int rank[NMAX];

int init(int num)
{
	int i;
	for(i=1;i<=num;i++)
	{
		fa[i]=rel[i]=0;
		rank[i]=1;
	}
}

void print()
{
	int i;
	for(i=1;i<=10;i++)
	{
		printf("(%d %d)",i,fa[i]);
	}
	printf("\n");
}
int find(int x)
{
	int root=x,tt;
	while(fa[root]!=0) root=fa[root];
	while(fa[x]!=0)
	{
		tt=fa[x];
		fa[x]=root;
		x=tt;
	}
	return root;
}

void add(int a,int b)
{	//合并含有a,b的集合
//	printf("add 1 a=%d b=%d\n",a,b);
	a=find(a);
	b=find(b);
	//a,b都是代表元
//	printf("add 2 a=%d b=%d\n",a,b);
	if(a!=b)
	{//a=b时合并，会出现fa[a]=a,会死循环
		if(rank[a]<rank[b])
		{
			fa[a]=b;
			rank[b]+=rank[a];
		}
		else
		{
			fa[b]=a;
			rank[a]+=rank[b];
		}
	}
//	print();
}

int solve(int num)
{
	int i,a,ans=0;
	for(i=1;i<=num;i++)
	{
		a=find(i);
		rel[a]++;//以a为代表元的集合，含有的元的个数
	}
	for(i=1;i<=num;i++)
	{
		if(rel[i]>0) ans++;
	}
	return ans;
}

int main()
{
	int num,cnum,i,a,b,j;
	scanf("%d %d",&num,&cnum);
	j=0;
	while(!(num==0 && cnum==0))
	{
		++j;
		init(num);
		for(i=1;i<=cnum;i++)
		{
			scanf("%d %d",&a,&b);
			add(a,b);
		}
		printf("Case %d: %d\n",j,solve(num));
		scanf("%d %d",&num,&cnum);
	}
	return 0;
}