首页 > 代码库 > POJ2492 A Bug's Life (并查集)

POJ2492 A Bug's Life (并查集)

本文出自:http://blog.csdn.net/svitter


题意:

给出昆虫编号,看昆虫能否交配,如果出现同性交配或者自我交配的情况,则出现BUG。

输入输出分析:

1.输入输出数据:

input:

2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

output:

Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

第一行给出的是测试数据的个数,随后跟着n, m。n是昆虫个数,m是关系个数。%d %d表示两个编号的昆虫进行交配。

输出数据中间存在空行。

*判断出BUG以后,继续读入测试数据。


题目分析:

这道题目和1291类似,但是相对简单。

可以如此想。

开一个N*2的数组,前N表示雄性,后N表示雌性。

%d %d分别为i, j 

那么 i 和 j 一定不属于同一集合,i+n和j+n一定也不属于同一集合。

如果属于同一集合,那么出现bug。


AC代码,TIME:829MS

//author: svtter
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

#define INF 0xffffff

using namespace std;

const int MAXN = 2000011; 
int root[MAXN];
int t;
int n, m;

void init()
{
    for(int i = 0; i <= n*2; i++)
        root[i] = i;
}

int getRoot(int i)
{
    if(i == root[i])
        return i;
    return root[i] = getRoot(root[i]);
}

void Merge(int i, int j)
{
    int a = getRoot(i);
    int b = getRoot(j);
    if(a == b)
        return;
    root[a] = b;
}

//judge same set
bool jud(int i, int j)
{
    return getRoot(i) == getRoot(j);
}

int main()
{
    int i, j;
    int t1, t2;
    bool flag;
    cin >> t;
    for(i = 1; i <= t; i++)
    {
        flag = false;

        //input
        scanf("%d%d", &n, &m);
        init();
        for(j = 0; j < m; j++)
        {
            scanf("%d%d",&t1, &t2);
            if(flag)
                continue;
            if(jud(t1, t2) || jud(t1+n, t2+n))
                flag = 1;
            else
            {
                Merge(t1, t2+n);
                Merge(t1+n, t2);
            }
        }

        //result
        printf("Scenario #%d:\n", i);
        if(flag)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");
        if(i != t)
            printf("\n");
    }

    return 0;
}