题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1829

题目描述

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.

思路

题目意思是给一堆虫子和关系,判断有没有同性恋。

并查集,每次将同性的放在一个集合中,例如雄性的放在一个集合,雌性的放在一个集合。然后每次判断两个虫子关系是否同性,同性则输出Suspicious bugs found!,若没有发现则输出No suspicious bugs found!

AC代码

/*************************************************************************
    > File Name: 1829.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-05 Sun 10:54:36 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int Set[2001]; // 虫子的集合,有两种,雌性和雄性
int oppo[2001]; // 相对于虫子的异性,例如虫子1的异性是oppo[1],0代表没有
bool flag; // 判断是否发现同性恋,没有flag为true,有flag为false

int find(int x) { // 查找集合(根节点)+路径压缩
    return x==Set[x] ? x:Set[x] = find(Set[x]); 
}
void unite(int a, int b) { // 合并
    a = find(a); 
    b = find(b);
    if(a==b) { // 若出现同性恋
        flag = false;
    }
    if(oppo[a]) Set[oppo[a]] = b; // 若a之前有异性的话,将a异性和b放在一个集合(即同性)
    if(oppo[b]) Set[oppo[b]] = a; // 同上
    oppo[a] = b; // 记录a的异性为b
    oppo[b] = a; // 同上
}

int main()
{
#ifdef Oj
    freopen("1829.in", "r", stdin);
#endif
    int T;
    cin >> T;
    int Case=0;
    while(T--) {
        int n, m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n; ++i)
            Set[i]=i, oppo[i]=0;
        flag = true;
        int a, b;
        for(int i=0; i<m; ++i) {
            scanf("%d%d", &a, &b);
            unite(a, b);
        }
        printf("Scenario #%d:\n", ++Case);
        if(flag)
            puts("No suspicious bugs found!\n");
        else
            puts("Suspicious bugs found!\n");
    }

    return 0;
}