hdu 1829 A Bug's Life(并查集)

简介:

A Bug's Life

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 364 Accepted Submission(s): 140

Problem 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!

分析:

(1)题意很简单,就是检查一堆数据中是否有同性恋,找出主要矛盾是如果1喜欢2,2喜欢3,而1又喜欢3,则矛盾。找出出现类的的矛盾

(2)这里用bugs数组存储其父亲节点的下标,用relation数组存储该虫子与根节点之间的关系。1为同性,0为异性。

(3)并查集详见注释

复制代码
#include <stdio.h>
//存储的是其父亲的下表
int bugs[2010];
int relation[2010];//1:相同性别 0:不同性别
//初始化
void init(int len)
{
    for(int i = 0;i <= len; i++)
    {
        bugs[i] = i;
        relation[i] = 1;
    }
}
//找到根
int find(int bug)
{
    if(bugs[bug]==bug)return bug;
    int tem = bugs[bug];
    bugs[bug] = find(bugs[bug]);//递归更新域,返回最终的父亲节点,把所有的孩子都更新了
    //注意这里,求当前位置和父亲的关系,记录之前父亲的位置为tem,然后因为是递归,
    //此时的relation[tem]已经在递归中更新过了,也就是孩子和父亲的关系+父亲和爷爷的关系+1然后模2就得到
    //孩子和爷爷的关系,这里用0和1表示,0表示不同性别,1表示相同性别
    relation[bug] = (relation[bug]+relation[tem]+1)%2;
    return bugs[bug];
}

void union_set(int a,int b,int x,int y)
{
    //合并,让前边的集合的根指向后边集合的根,成为一个集合
    bugs[x]=y;
    //更新前边集合根和新的集合根之间的关系,
    //注意这里,relation[a]+relation[x]与relation[b]
    //相对于新的父节点必须相差1个等级,因为他们不是gay
    relation[x] = (relation[b]-relation[a])%2;
}

int main()
{
    int S;
    int n,inter;
    int bug1,bug2,parent1,parent2;
    bool flag;//false:无同性恋,true:有同性恋
    scanf("%d",&S);
    for(int i=1; i<=S;i++)
    {
        scanf("%d%d",&n,&inter);
        flag = false;
        init(n);//初始化,使其父节点为自己
        for(int j = 1; j <= inter; j++)
        {
            scanf("%d%d",&bug1,&bug2);
            if(flag)continue;
            parent1 = find(bug1);
            parent2 = find(bug2);
            if(parent1==parent2)
            {
                if(relation[bug1]==relation[bug2])//同性
                flag = true;
            }
            union_set(bug1,bug2,parent1,parent2);
        }
        if(flag)
        printf("Scenario #%d:\nSuspicious bugs found!\n",i);
        else
        printf("Scenario #%d:\nNo suspicious bugs found!\n",i);
        printf("\n");
    }
    return 0;
}
复制代码

 

 






本文转自NewPanderKing51CTO博客,原文链接:http://www.cnblogs.com/newpanderking/archive/2012/10/12/2721799.html ,如需转载请自行联系原作者



相关文章
|
开发框架 .NET
poj 3468 A Simple Problem with Integers线段树区间修改
题目意思很简单,有N个数,Q个操作, Q l r 表示查询从l到r 的和,C l r v 表示将从l到r 的值加上v,明显的线段树,不知道线段树的人肯定暴力,肯定超时,哈哈!!
33 0
|
网络架构
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
|
人工智能 Java
[HDU 7136] Jumping Monkey | 并查集 | 逆向思维
Jumping Monkey Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 747 Accepted Submission(s): 360
225 0
[HDU 7136] Jumping Monkey | 并查集 | 逆向思维
|
定位技术
HDOJ/HDU 1180 诡异的楼梯(经典BFS-详解)
HDOJ/HDU 1180 诡异的楼梯(经典BFS-详解)
131 0
HDOJ/HDU 1180 诡异的楼梯(经典BFS-详解)
POJ-2492,A Bug's Life(分类并查集)
POJ-2492,A Bug's Life(分类并查集)
HDOJ(HDU) 2078 复习时间
HDOJ(HDU) 2078 复习时间
133 0