首页 > 代码库 > poj-2492- A Bug's Life

poj-2492- A Bug's Life

这个题题意很好理解:输入样例数T,然后每组数据首先输入bug的个数n和m,bug编号为1——n!然后接下来输入m组互为异性的bug的编号a和b,然后要求我们判断这组数据里是否存在一组同性的bug,与给出的数据矛盾,然后输出对应结果;如果不存在,则输出另外一种结果!


题解:这道题使用并查集即可,每次处理a和b之前需要判断一下a和b之前是否已经和其它的异性bug交配过!然后每次处理完a和b之后判断a和b是否是属于树的同一条分支的,如果是则证明a和b是同性bug!

代码如下:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int yix[2014],f[2014];
void init(int n)
{
    for(int i=1; i<=n; i++)
    {
        f[i]=i;
        yix[i]=0;
    }
}
int find(int x)
{
    return f[x]==x?x:find(f[x]);
}
void unity(int a,int b)
{//合并同性的bug
    int x=find(a);
    int y=find(b);
    if(x!=y)
        f[x]=y;
}
int main()
{
    int T;
    cin>>T;
    for(int i=1; i<=T; i++)
    {
        bool tx_istrue=false;
        int n,m,a,b;
        cin>>n>>m;
        init(n);
        while(m--)
        {
            //如果yix[num]不为0的话表示num肯定与编号为yix[num]的异性bug交配过!
            cin>>a>>b;
            if(!yix[a]&&!yix[b])
            {
                yix[a]=b;//如果这两只bug前面都没有出现过,
                yix[b]=a;//则标记数组分别标记对方为异性!
            }
            else if(!yix[a]&&yix[b])
            {
                yix[a]=b;
                unity(a,yix[b]);//编号为a的bug肯定与编号为yix[b]的bug同性!
            }
            else if(yix[a]&&!yix[b])
            {
                yix[b]=a;
                unity(b,yix[a]);//编号为b的bug肯定与编号为yix[a]的bug同性!
            }
            else
            {//此处即我上面所说的判断,在这表明a和b之前都分别与编号为yix[a]和yix[b]的异性bug交配过!
                unity(yix[a],b);
                unity(yix[b],a);
            }
            if(find(a)==find(b))
                tx_istrue=true;//每输入一次就就行一次判断,判断a和b是否是同性!
        }
        printf("Scenario #%d:\n",i);
        if(tx_istrue)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");
        printf("\n");

    }
    return 0;
}


poj-2492- A Bug's Life