| ||||||||||
| 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 | |||||||||
HELP!! 貌似测试数据都过了 可就老WA#include<iostream>
using namespace std;
int find(int x);
void bing(int fa,int fb,int a,int b);
int father[3003],du[3003];
bool sex[3003];
int main(void)
{
int w,n,i,num,in,a,b,fa,fb,q;
cin>>n;
for(w=1;w<=n;w++)
{
scanf("%d%d",&num,&in);
for(i=1;i<=num;i++)
{
father[i]=i;
du[i]=1; //深度
sex[i]=false; //false代表与头结点性别一致,true代表不同
}
q=0;
while(in--)
{
scanf("%d%d",&a,&b);
if(q==0)
{
fa=find(a);
fb=find(b);
if(fa!=fb)
{
bing(fa,fb,a,b);
}
else
{
if(sex[a]==sex[b])
{
q=1;
}
}
}
}
if(in==-1&&q==0)
{
cout<<"Scenario #"<<w<<":"<<endl;
cout<<"No suspicious bugs found!"<<endl<<endl;
}
else
{
cout<<"Scenario #"<<w<<":"<<endl;
cout<<"Suspicious bugs found!"<<endl<<endl;
}
}
return 0;
}
int find(int x) //不带压缩路劲 为了更新各结点性别方便
{
int k;
k=x;
if(x!=father[x])
{
k=find(father[x]);
sex[x]=!sex[k]; //从头结点(father结点)开始,以头结点为准更新以下的结点的性别
}
return k;
}
void bing(int fa,int fb,int a,int b)
{
if(du[fa]>du[fb])
{
father[fb]=fa;
sex[fb]=!(sex[a]^sex[b]); //更新性别
}
else
{
father[fa]=fb;
sex[fa]=!(sex[a]^sex[b]);
}
if(du[fa]==du[fb])
{
du[fb]=du[fb]+1;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator