Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

留下足迹

Posted by Heng_Xing at 2011-08-09 17:06:26 on Problem 1611
#include<stdio.h>
int p[30001];
int num[30001];

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

void union_set(int a,int b)
{
	int x,y;
	x=find_set(a);
	y=find_set(b);
	if(x==y)
		return ;
	if(num[x]>num[y])
	{
		p[y]=x;
		num[x]+=num[y];
	}
	else
	{
		p[x]=y;
		num[y]+=num[x];
	}
}

int main (void)
{
	int n,m;
	int t;
	int x,y;
	int i;
	while(scanf("%d %d",&n,&m),n||m)
	{
		for(i=0;i<n;i++)
		{
			p[i]=i;
			num[i]=1;
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d",&t);
			t--;
			scanf("%d",&x);
			while(t--)
			{
				scanf("%d",&y);
				union_set(x,y);
			}
		}
		x=find_set(0);
		printf("%d\n",num[x]);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator