POJ – 2492 – A Bug’s Life (种类并查集)

2017年11月2日 0 条评论 14 次阅读 1 人点赞

题目链接: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;
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)