DLKKILL

DLKKILL's world

POJ - 2492 - A Bug's Life (种类并查集)

题目链接:POJ – 2492

题目大意:

一种动物有两种性别,假设不同性别才能进行配对,

给出配对情况,问是否存在同性配对的情况。

题目分析:

种类并查集。

用a和a+n代表两种性别。

如果a和b在一个并查集内,则同性。

给出代码:

#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int maxn=4000+10;
int pre[maxn];
int deg[maxn];
void init()
{
    for(int i=0;i<maxn;i++)
    {
        pre[i]=i;
        deg[i]==0;
    }
}
int finds(int x)
{
    if(pre[x]==x)
        return x;
    else
        return pre[x]=finds(pre[x]);
}
bool same(int x,int y)
{
    return finds(x)==finds(y);
}
void unite(int x,int y)
{
    if(same(x,y))
        return;
    x=finds(x);
    y=finds(y);
    if(deg[x]<deg[y])
    {
        pre[x]=y;
    }
    else
    {
        pre[y]=x;
        if(deg[x]==deg[y])
            deg[x]++;
    }
    return;
}
int main()
{
   int T;
   scanf("%d",&T);
   int kase=0;
   while(T--)
   {
       int flag=0;
       init();
       int n,m;
       scanf("%d%d",&n,&m);
       while(m--)
       {
           int a,b;
           scanf("%d%d",&a,&b);
           if(same(a,b))
           {
               flag=1;
               continue;
           }
           else
           {
               unite(a,b+n);
               unite(a+n,b);
           }
       }
       printf("Scenario #%d:\n",++kase);
       if(flag)
         printf("Suspicious bugs found!\n\n");
       else
        printf("No suspicious bugs found!\n\n");
   }
   return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注