| ||||||||||
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<iostream> using namespace std; const int size=3005; int parent[size],rank[size]; bool found; int findset(int x,int &h,int &c) { h=0; c=-1; while(x!=parent[x]) { h++; c=x; x=parent[x]; } return x; } void unionset(int x,int y) { int r1,c1,h1; int r2,c2,h2; r1=findset(x,h1,c1); r2=findset(y,h2,c2); if(r1==r2) { if(h1-h2%2==0) found=1; return; } if(h1-h2%2==0) { if(rank[r1]==rank[r2]) { parent[r2]=r1; rank[r1]++; } else if(rank[r1]>rank[2]) parent[r2]=r1; else parent[r1]=r2; } else { if(rank[r1]>=rank[r2]) { parent[r2]=c1; rank[r1]=rank[r2]+2>rank[r1]?rank[r2]+2:rank[r1]; } else { parent[r1]=c2; rank[r2]=rank[r1]+2>rank[r2]?rank[r1]+2:rank[r2]; } } } int main() { int t,e; while(scanf("%d",&t)==1) { e=1; while(t--) { int i; int x,y; int n,m; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { parent[i]=i; rank[i]=0; } found=0; for(i=0;i<m;i++) { scanf("%d%d",&x,&y); if(found) continue; unionset(x,y); } printf("Scenario #%d:\n",e); if(found) printf("Suspicious bugs found!\n"); else printf("No suspicious bugs found!\n"); if(t) printf("\n"); e++; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator