NUAA ACM OJ源码

				#include 
				#include 
				#include 
				
				#define NMAX 50010
				//POJ 2524 并查集
				int fa[NMAX];
				int rel[NMAX];
				int rank[NMAX];
				
				int init(int num)
				{
					int i;
					for(i=1;i					{
						fa[i]=rel[i]=0;
						rank[i]=1;
					}
				}
				
				void print()
				{
					int i;
					for(i=1;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]						{
							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					{
						a=find(i);
						rel[a]++;//以a为代表元的集合，含有的元的个数
					}
					for(i=1;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						{
							scanf("%d %d",&a,&b);
							add(a,b);
						}
						printf("Case %d: %d\n",j,solve(num));
						scanf("%d %d",&num,&cnum);
					}
					return 0;
				}