学步园

pku 1182的简单版，也是用树形结构来存储相对关系。

 对于有些情况，这道题可以在没有输入所有数据前得到答案，我就是因为提前break了，结果一直WA。对于这种多CASE的问题，得把每个CASE的输入好好读完再去处理下面的。

#include <iostream><br /> using namespace std;<br /> int parent[2002];<br /> bool relation[2002];<br /> void Union(int a,int b,bool flag)<br /> {<br /> parent[a]=b;<br /> relation[a]=flag;<br /> }<br /> int main()<br /> {<br /> bool exist;<br /> int scenario,N,K,first,second,first_flag,second_flag;<br /> scanf("%d",&scenario);<br /> for(int i=0;i<scenario;i++)<br /> {<br /> scanf("%d%d",&N,&K);<br /> for(int j=1;j<=N;j++)<br /> {<br /> parent[j]=-1;<br /> }<br /> exist=false;<br /> for(int j=0;j<K;j++)<br /> {<br /> scanf("%d%d",&first,&second);<br /> if(exist) continue;<br /> first_flag=0;<br /> second_flag=0;<br /> while(parent[first]>0)//查找代表节点，计算和代表节点的关系。<br /> {<br /> if(relation[first]) first_flag++;<br /> first=parent[first];<br /> }<br /> while(parent[second]>0)<br /> {<br /> if(relation[second]) second_flag++;<br /> second=parent[second];<br /> }<br /> if(first!=second)<br /> {<br /> if((first_flag-second_flag)%2==0) Union(first,second,true);<br /> else Union(second,first,false);<br /> }<br /> else<br /> {<br /> if((second_flag-first_flag)%2==0) exist=true;<br /> }<br /> }<br /> printf("Scenario #%d:/n",i+1);<br /> if(exist) printf("Suspicious bugs found!/n/n");<br /> else printf("No suspicious bugs found!/n/n");<br /> }<br /> return 0;<br /> }<br />