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