| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
find() 压缩路径不对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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator