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

这么经典的题目怎么就tle?

Posted by y05zh at 2007-08-21 17:56:17 on Problem 2492
#include<iostream>
using namespace std;
#define max 2005
int a[max],b[max];
inline int set(int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		a[i]=0;
		b[i]=-1;
	}
	return 0;
}
inline int find(int x)
{
	int i;
	for(i=x;b[i]>=0;i=b[i]);
	while(i!=x)
	{
		int tmp=b[x];
		b[x]=i;
		x=tmp;
	}
	return i;
}
inline int Union(int x,int y)
{
	//if(x==y)return 0;
	int tmp=b[x]+b[y];
	if(b[x]>b[y])
	{
		b[y]=tmp;
		b[x]=y;
	}
	else
	{
		b[x]=tmp;
		b[y]=x;
	}
	return 0;
}

int main()
{
	int sce;
	int s;
	int x,y;
	int n,m;
	int px,py;
	int flag=0;
	int i;
	scanf("%d",&sce);
	for(s=1;s<=sce;s++)
	{
		printf("Scenario #%d:\n",s);
		scanf("%d%d",&n,&m);
		flag=0;
		set(n);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			px=find(x);
			py=find(y);
			if(px==py)
			{
				flag=1;
				break;
			}
			else
			{
				if(a[x]!=0)
				{
					int ax=find(a[x]);
					//if(ax==py)continue;
					Union(ax,py);
					//continue;
				}
				if(a[y]!=0)
				{
					int ay=find(a[y]);
					//if(ay==px)continue;
					Union(px,ay);				
				}
				a[x]=py;
				a[y]=px;
				
			}
		}
		for(i=i+1;i<m;i++)scanf("%d%d",&x,&y);
		if(flag==1)
		{
			printf("Suspicious bugs found!\n");
		}
		else
		{
			printf("No suspicious bugs found!\n");
		}
		printf("\n");
	}
	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