| ||||||||||
| 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 | |||||||||
最近在做并查....代码留给路人..#include "stdio.h"
#include "memory.h"
int next[2001],num[2001],father[2001];
void make_set(int n)
{
father[0]=0;
num[0]=0;
for(int i=1;i<=n;++i)
{
father[i]=i;
num[i]=1;
}
memset(next,0,sizeof(next));
}
int find_set(int x)
{
while(x!=father[x])
x=father[x];
return x;
}
int Union(int x,int y)
{
next[x]=next[y]=0;
if(x==y) return x;
if(num[x]>num[y])
{
father[y]=x;
num[x]+=num[y];
num[y]=0;
return x;
}
else
{
father[x]=y;
num[y]+=num[x];
num[x]=0;
return y;
}
}
int main(void)
{
int i,j,k,Case,n,m,flag,a,b,k1,k2,next1,next2;
scanf("%d",&Case);
for(i=0;i!=Case;++i)
{
flag=0;
scanf("%d%d",&n,&m);
make_set(n);
while(m--)
{
scanf("%d%d",&a,&b);
if(a>n||b>n) flag=1;
a=find_set(a);
b=find_set(b);
if(a==b) flag=1;
else if(next[a]!=0&&next[b]!=0)
{
next1=next[a];
next2=next[b];
k1=Union(next1,b);
k2=Union(next2,a);
next[k1]=k2;
next[k2]=k1;
}
else if(next[a]!=0)
{
k1=Union(next[a],b);
next[k1]=a;
next[a]=k1;
}
else if(next[b]!=0)
{
k1=Union(next[b],a);
next[k1]=b;
next[b]=k1;
}
else
{
next[a]=b;
next[b]=a;
}
}
if(flag==1)
{
printf("Scenario #%d:\nSuspicious bugs found!\n\n",i+1);
}
else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",i+1);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator