/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:梁岳传
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////

#include<iostream>
using namespace std;
#define MAX 1000010
int ary[MAX];
int opt[MAX];
void Init(int n)
{
    int i;
    for(i = 0; i <= n+10; ++i)
    {
        ary[i] = -1;
        opt[i] = -1;
    }
}
int Find(int index)
{
    if(ary[index] < 0)
        return index;
    return ary[index] = Find(ary[index]);
}
int Union(int first, int second)
{
    int i, j;
    if(second == -1)
        return first;

    i = Find(first);
    j = Find(second);
    if(i == j)
        return i;
    if(ary[i] < ary[j])
    {
        ary[i] += ary[j];
        ary[j] = i;
        return i;
    }
    else
    {
        ary[j] += ary[i];
        ary[i] = j;
        return j;
    }
    return -1;
}
void UnionDiff(int first, int second)
{
    int r1, r2, d1, d2;
    r1 = Find(first);
    r2 = Find(second);
    if(r1 == r2)
        return;
    d1 = Union(r1, opt[r2]);
    d2 = Union(r2, opt[r1]);
    opt[d1] = d2;
    opt[d2] = d1;
}
int main(int argv, char* argc[])
{
    int vexs, edges, tests, ct;
    int i, first, second;
    bool flag;
    cin>>tests;
    ct = 1;
    while(tests--)
    {
        scanf("%d%d", &vexs, &edges);
        Init(vexs);
        flag = false;
        for(i = 0; i < edges; ++i)
        {
            cin>>first>>second;
            if(Find(first) == Find(second))
                flag = true;
            else
                UnionDiff(first, second);
        }
        cout<<"Scenario #"<<ct<<":"<<endl;
        if(flag == true)
            cout<<"Suspicious bugs found!"<<endl<<endl;
        else
            cout<<"No suspicious bugs found!"<<endl<<endl;
        ct++;
    }
    return 0;
}

评论