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 31102149 at 2011-07-16 20:39:48 on Problem 1611
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

#define MAX 30010

long int father[MAX];
long int s[MAX];
int flag[MAX];

long int finds(long int x)
{
	if(x!=father[x])
	{
		father[x]= finds(father[x]);
	}
	return father[x];
}

int main()
{
	long int i,j,m,n,k,q,mas;
	while(scanf("%ld %ld",&m,&n)&&(n||m))
	{
		memset(flag,0,sizeof(flag));
		q= 0;
		for(i= 0;i<m;i++)
		{
			father[i]= i;
		}
		for(i=0;i<n;i++)
		{
			mas= 30001;
			scanf("%ld",&k);
			for(j=0;j<k;j++)
			{
				scanf("%ld",&s[j]);
				flag[s[j]]= 1;
				if(mas>finds(s[j]))
				{
					mas= finds(s[j]);
				}
			}
			for(j=0;j<k;j++)
			{
				father[finds(father[s[j]])]= mas;
			}
			
		}
		flag[0]= 1;
		for(i= 1;i<m;i++)
		{
			if(flag[i])
			father[i]= finds(i);
		}
		for(i=0;i<m;i++)
		{
			if(flag[i])
			{
				if(father[i]==0)
				{
					q++;
				}
			}
		}
		printf("%ld\n",q);
	}
	
	
	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