我的个人记载
  • About Me
不知名小站
Never Give Up
  1. 首页
  2. kuangbin并查集专题
  3. 正文

J - A Bug's Life

2020年01月29日 89点热度 0人点赞 0条评论

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!

Hint
Huge input,scanf is recommended.

题意:
给定n只虫子 不同性别的可以在一起 相同性别的不能在一起
给你m对虫子 判断中间有没有同性别在一起的;
我们把同性的放到一个集合里 如果一个集合里出现了异性 则说明存在同性恋在一起
假设 x 为一种性别 x + n 为与其相反的性别
若a,b为同性 的 我们则可以把判断 (a,b+n) (b,a+n)为异性反之亦然;

题解:
扩展域并查集

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 4010;
int p[maxn];
int t, n, m;

int find(int x){
  return p[x] != x ? p[x] = find(p[x]) : p[x];
}

void Union(int a, int b){
  int x = find(a);
  int y = find(b);
  if(x != y)  p[x] = y;
}

bool judge(int x, int y){
  x = find(x);
  y = find(y);
  if(x != y)  return true;
  else return false;
}

int main()
{
  scanf("%d",&t);

  for(int i = 1; i <= t; i ++){
    scanf("%d%d",&n,&m);
    for(int i = 0; i <= 2 * n; i ++)
      p[i] = i;
    bool f = 1;
    int x, y;
    while(m --){
      scanf("%d%d",&x,&y);
      if(judge(x, y) || judge(x + n , y + n)){
        Union(x, y + n);
        Union(x + n, y);
      }
      else
        f = 0;
    }
    if(i != 1)  puts(" ");
    printf("Scenario #%d:\n", i);
    puts(f ? "No suspicious bugs found!" : "Suspicious bugs found!");
  }
  return 0;
}
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020年05月02日

框框

喜欢算法,喜欢编程。

打赏 点赞
< 上一篇
下一篇 >

文章评论

取消回复

框框

喜欢算法,喜欢编程。

文章归档
  • 2021年1月
  • 2020年10月
  • 2020年8月
  • 2020年7月
  • 2020年1月
  • 2019年11月
  • 2019年8月
  • 2019年7月
分类目录
  • 2008年哈尔滨区域赛
  • 2018焦作网络赛
  • Greater New York Region 2014
  • kuangbin并查集专题
  • Kuangbin数论专题
  • NZPC 2017
  • upc个人训练赛
  • 位运算
  • 博弈论
  • 多校训练
  • 搜索
  • 数据结构
  • 数论
  • 杭电多校训练第五场
  • 深入理解计算机基础/CSAPP
  • 算法模板
  • 线段树
  • 训练赛

COPYRIGHT © 2020 我的个人记载. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

苏ICP备19034952号-1