| ||||||||||
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 |
TLE求解 关系型并查集#include <string.h> #include <stdio.h> #include <stdlib.h> #define N 2001 int bleg[N],dis[N],hash[N]; void unit () { for(int i=0;i<N;i++) { bleg[i]=i; dis[i]=0; } } int find(int x) { int y=x,cnt=0; while(y!=bleg[y]) { y=bleg[y]; cnt+=bleg[y]; } while(x!=bleg[x]) { int px=bleg[x]; int temp=dis[x]; dis[x]=cnt; bleg[x]=y; cnt-=temp; x=px; } return y; } void Union(int x,int y) { int bx=find(x); int by=find(y); if(bx==by) return; if(rand()%2) { dis[bx]=dis[x]+dis[y]+1; bleg[bx]=by; } else { dis[by]=dis[x]+dis[y]+1; bleg[by]=bx; } } int main() { int x,y,t,cnt,n,m,flag; while(~scanf("%d",&t)) { cnt=0; while(t--) { cnt++;flag=0;unit(); memset(hash,0,sizeof(hash)); scanf("%d %d",&n,&m); while(m--) { scanf("%d %d",&x,&y); if(hash[x]==1&&hash[y]==1) { if((dis[x]+dis[y])%2) flag=1; } else {Union(x,y); hash[x]=hash[y]=1;} } if(flag==1) printf("Scenario #%d:\nSuspicious bugs found!\n\n",cnt); else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",cnt); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator