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