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

find() 压缩路径不对

Posted by sunmoonstar_love at 2006-09-08 18:13:09 on Problem 2492
In Reply To:为什么我用并查集,压缩了路径可还是TLE呢!?? Posted by:zhenly at 2006-09-08 17:15:08
> 我的程序:
> 
> #include<stdio.h>
> #define MAX 2001
> int parent[MAX];
> void set(int n);
> int find(int x);
> void unit(int i,int j);
> void main()
> {
> 	int N,i,j,n,m,b1,b2,flag;
> 	scanf("%d",&N);
> 	for(i=0;i<N;i++)
> 	{
> 		flag=0;
> 		scanf("%d%d",&n,&m);
> 		set(n);
> 		for(j=0;j<m;j++)
> 		{
> 			scanf("%d%d",&b1,&b2);
> 			if(flag==0)
> 			{
> 				if(find(b1)==find(b2))
> 					flag=1;
> 				else
> 					unit(find(b1),find(b2));
> 			}
> 		}
> 		printf("Scenario #%d:\n",i+1);
> 		if(flag==1)
> 			printf("Suspicious bugs found!\n");
> 		else
> 			printf("No suspicious bugs found!\n");
> 	}
> }
> void set(int n)
> {
> 	int i;
> 	for(i=0;i<=n;i++)
> 		parent[i]=-1;
> }
> int find(int x)
> {
> 	int i,temp;
> 	if(parent[x]>0)
> 		i=find(parent[x]);
> 	while(i!=x)//压缩路径!
> 	{
> 		temp=parent[x];
> 		parent[x]=i;
> 	}
> 	return i;
> }
> void unit(int i,int j)
> {
> 	int temp;
> 	temp=parent[i]+parent[j];
> 	if(parent[i]>parent[j])
> 	{
> 		parent[j]=temp;
> 		parent[i]=j;
> 	}
> 	else
> 	{
> 		parent[i]=temp;
> 		parent[j]=i;
> 	}
> }

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