///////////////////////////////////////////作品名称:并查集应用//作者姓名:梁岳传//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<iostream>using namespace std;#define MAX 1000010int 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;}

评论