#include<iostream>
using namespace std;
#define MAXN 50000

int parent[MAXN+1];

void init(int n)
{
	int i;
	for(i=1;i<=n;i++)
		parent[i]=-1;
}


int find(int x)
{
	/*不知道是不是我的压缩有问题
	int tmp,
		p=x;
	while(parent[p]>0)
		p=parent[x];      //p==root
	while(x!=p)
	{
		tmp=parent[x];
		parent[x]=p;
		x=tmp;
	}
	return p;
	*/下面是不压缩的
	if(parent[x]<0)
		return x;
	else return find(parent[x]);
}

void Union(int x,int y)
{
	int root1=find(x),
		root2=find(y);
	if(root1==root2) return;
	if(parent[root1]<parent[root2])
	{
		parent[root1]+=parent[root2];
		parent[root2]=root1;
	}else{
		parent[root2]+=parent[root1];
		parent[root1]=root2;
	}
}


int main()
{
	int n,m,x,y,i,k=1,sum;
	memset(parent,-1,sizeof(parent));
	while( scanf("%d%d",&n,&m)==2 && n!=0 )
	{
		//init(n);
		sum=0;
		while(m--)
		{
			scanf("%d%d",&x,&y);
			Union(x,y);
		}
		for(i=1;i<=n;i++)
		{
			if(parent[i]<0)
				sum++;
			parent[i]=-1;
		}
		printf("Case %d: %d\n",k++,sum);
	}
}

• Re:压缩超时，不压AC...什么问题，谁帮优化下...谢谢 (7) D1000371 2011-05-22 19:11:27