POJ-2492,A Bug's Life(分类并查集)

简介: POJ-2492,A Bug's Life(分类并查集)

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

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.


Input:


The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.


Output:



The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.


Sample Input:


2


3 3


1 2


2 3


1 3


4 2


1 2


3 4


Sample Output:


Scenario #1:


Suspicious bugs found!


Scenario #2:


No suspicious bugs found!


程序代码:


#include<iostream>
#include<cstdio>
using namespace std;
#define N 2000000
int f[N+1];
int getf(int v)
{
  if(f[v]==v)
    return v;
  else
  {
    f[v]=getf(f[v]);
    return f[v];
  }
}
void merge(int v,int u)
{
  int t1=getf(v);
  int t2=getf(u);
  if(t1!=t2)
    f[t2]=t1;
  return ;
}
int main()
{
  int t,n,m,a,b,ans=1;
  scanf("%d",&t);
  while(t--)
  {
    int flag=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=N;i++)
      f[i]=i;
    while(m--)
    {
      scanf("%d %d",&a,&b);
      if(flag==1)
        continue;
      if(getf(a)==getf(b)||getf(a+n)==getf(b+n))
      {//根节点一样,代表性别相同 
        flag=1;
        continue;
      }
      else
      {//合并 
        merge(a,b+n);
        merge(a+n,b);
      }
    }
    printf("Scenario #%d:\n",ans++);
    if(flag==1)
      printf("Suspicious bugs found!\n\n");
    else
      printf("No suspicious bugs found!\n\n");
  }
  return 0;
}

 


目录
打赏
0
0
0
0
85
分享
相关文章
The kth great number(小根堆思想,模板题)
The kth great number(小根堆思想,模板题)
65 0
六六力扣刷题回溯之combinations(组合)
前言 之前小六六一直觉得自己的算法比较菜,算是一个短板吧,以前刷题也还真是三天打鱼,两台晒网,刷几天,然后就慢慢的不坚持了,所以这次,借助平台的活动,打算慢慢的开始开刷,并且自己还会给刷的题总结下,谈谈自己的一些思考,和自己的思路等等,希望对小伙伴能有所帮助吧,也可以借此机会把自己短板补一补,希望自己能坚持下去呀
180 0
[ICPC 46th Shanghai] Life is a Game 克鲁斯卡尔重构树
题目大意: 给定n个点,m条边,有q个询问 每个点有一个(能量值)点权,每条边有一个边权 m条边描述为u v w表示有一条u与v相连的边权为w的通路 在每一次询问中,给定一个点x和现有的能量值k,每次只能是在当前能量值大于边权的时候到达另一个点,并获取这个点的能量值(路可以重复走),问最终能够获得多大的能量值
145 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等