| ||||||||||
| 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<iostream>
using namespace std;
int father[2005];
int rela[2005];
int flag;
int N,cas;//虫子数,案例数
int Find(int x)
{
int px;
if(x==father[x]) return x;
px=Find(father[x]);
rela[x]=(rela[x]+rela[father[x]])%2;
return father[x]=px;
}
void Union(int x,int y)//0表示同性,1表示异性
{
int px,py;
px=Find(x);
py=Find(y);
if(px==py)
{
if(rela[x]==rela[y])//与根节点的关系相同,那这个虫子必然同性
flag=1;
return;
}
else//不同就连上
{
father[px]=py;
rela[px]=(rela[y]-1-rela[x]+2)%2;
}
return;
}
void ini()
{
int i;
for(i=1;i<=N;i++)
{
father[i]=i;
rela[i]=0;//自己和自己肯定是同性
}
flag=0;
}
int main()
{
int t,i,j=1;
int x,y;//两个虫子
int tem;
scanf("%d",&t);
while(t--)
{
tem=0;
scanf("%d%d",&N,&cas);
ini();
for(i=1;i<=cas;i++)
{
scanf("%d%d",&x,&y);
Union(x,y);
if(flag==1)
{
tem=1;
}
}
if(tem)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",j++);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",j++);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator