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 pengshihui at 2010-07-29 09:10:44 on Problem 2492
#include "stdio.h"
#include "memory.h"
int next[2001],num[2001],father[2001];
void make_set(int n)
{
	father[0]=0;
	num[0]=0;
	for(int i=1;i<=n;++i)
	{
		father[i]=i;
		num[i]=1;
	}
	memset(next,0,sizeof(next));
}
int find_set(int x)
{
	while(x!=father[x])
		x=father[x];
	return x;
}
int Union(int x,int y)
{
	next[x]=next[y]=0;
	if(x==y) return x;
	if(num[x]>num[y])
	{
		father[y]=x;
		num[x]+=num[y];
		num[y]=0;
		return x;
	}
	else
	{
		father[x]=y;
		num[y]+=num[x];
		num[x]=0;
		return y;
	}
}
int main(void)
{
	int i,j,k,Case,n,m,flag,a,b,k1,k2,next1,next2;
	scanf("%d",&Case);
	for(i=0;i!=Case;++i)
	{
		flag=0;
		scanf("%d%d",&n,&m);
		make_set(n);
		while(m--)
		{
			scanf("%d%d",&a,&b);
			if(a>n||b>n) flag=1;
			a=find_set(a);
			b=find_set(b);
			if(a==b) flag=1;
			else if(next[a]!=0&&next[b]!=0)
			{
				next1=next[a];
				next2=next[b];
				k1=Union(next1,b);
				k2=Union(next2,a);
				next[k1]=k2;
				next[k2]=k1;
			}
			else if(next[a]!=0)
			{
				k1=Union(next[a],b);
				next[k1]=a;
				next[a]=k1;
			}
			else if(next[b]!=0)
			{
				k1=Union(next[b],a);
				next[k1]=b;
				next[b]=k1;
			}
			else
			{
				next[a]=b;
				next[b]=a;
			}
		}
		if(flag==1)
		{
			printf("Scenario #%d:\nSuspicious bugs found!\n\n",i+1);
		}
		else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",i+1);
	}
	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