首页 > 代码库 > POJ2492 A Bug's Life (easy)
POJ2492 A Bug's Life (easy)
Description
Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.
题目大意:n个昆虫,m组关系,每组关系给出的两个昆虫属于不同的性别,判断是否有Suspicious(连poj都这么。。。美丽。。。?)
思路:类似与团伙的题目,简单并查集的应用。。。
code:
题目大意:n个昆虫,m组关系,每组关系给出的两个昆虫属于不同的性别,判断是否有Suspicious(连poj都这么。。。美丽。。。?)
思路:类似与团伙的题目,简单并查集的应用。。。
code:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int fa[2001]={0},enemy[2001]={0};
int rool(int x)
{
if (fa[x]!=x) fa[x]=rool(fa[x]);
return fa[x];
}
int main()
{
int i,j,t,n,m,ci,a,b,r1,r2;
bool f;
cin>>t;
for (ci=1;ci<=t;++ci)
{
scanf("%d%d",&n,&m);
memset(enemy,0,sizeof(enemy));
for (i=1;i<=n;++i)
fa[i]=i;
f=false;
for (i=1;i<=m;++i)
{
scanf("%d%d",&a,&b);
if (rool(a)==rool(b)) f=true;
if (!f)
{
if (enemy[a]==0) enemy[a]=b;
else
{
r1=rool(enemy[a]);
r2=rool(b);
fa[r1]=r2;
}
if (enemy[b]==0) enemy[b]=a;
else
{
r1=rool(a);
r2=rool(enemy[b]);
fa[r1]=r2;
}
}
}
printf("%s%d%s\n","Scenario #",ci,":");
if (!f) printf("%s\n\n","No suspicious bugs found!");
else printf("%s\n\n","Suspicious bugs found!");
}
}
POJ2492 A Bug's Life (easy)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。