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