2013年10月3日 星期四

2013/10/3 POJ 2492 A Bug's Life

// http://poj.org/problem?id=2492
#include <iostream>
#include <cstdio>

using namespace std;

int p[4001];

int find_root(int x)
{
    if( x != p[x] )
        p[x] = find_root(p[x]);

    return p[x];
}

int main()
{
    int T, cnt;
    scanf("%d", &T); cnt = 0;

    while( cnt != T )
    {
        bool TRUE = true;

        if( cnt ) printf("\n");
        cnt++;
        printf("Scenario #%d:\n", cnt);

        int N, M;
        scanf("%d %d", &N, &M);

        for(int i = 0; i <= 2*N; i++)
        {
            p[i] = i;
        }

        while( M-- )
        {
            int a, b;
            scanf("%d %d", &a, &b);




            if( find_root(a) == find_root(b) ){ TRUE = false; }
            else
            {
                p[find_root(a)] = find_root(b+N);
                p[find_root(b)] = find_root(a+N);
            }
        }

        if( TRUE )
            printf("No suspicious bugs found!\n");
        else
            printf("Suspicious bugs found!\n");
    }
}

沒有留言:

張貼留言