| ||||||||||
| 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