首页 > 代码库 > hdu1829 A Bug's Life 基础种类并查集

hdu1829 A Bug's Life 基础种类并查集

  题目的大意可以理解为:A爱B,B爱C ……给出一系列爱恋的关系,推断有没有同性恋。

  思路是把相同性别的归为一个集合,异性的异性为同性。

  

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=2010;int f[N], r[N], flag;void init(){    for(int i=1;i<N;i++)    {        f[i]=i;        r[i]=0;    }}int Find(int x){    if(x==f[x]) return x;    return f[x]=Find(f[x]);}void Link(int x,int y){    int a=Find(x), b=Find(y);    if(a==b) flag=0;    else    {        if(r[x]) f[y]=Find(r[x]);        else r[x]=y;        if(r[y]) f[x]=Find(r[y]);        else r[y]=x;    }}int main(){    //freopen("test.txt","r",stdin);    int x,y,n,m,cas,k;    scanf("%d",&cas);    for(k=1;k<=cas;k++)    {        scanf("%d%d",&n,&m);        init();        flag=1;        while(m--)        {            scanf("%d%d",&x,&y);            if(!flag) continue;            Link(x,y);        }        printf("Scenario #%d:\n",k);        if(flag) printf("No suspicious bugs found!\n");        else printf("Suspicious bugs found!\n");        printf("\n");    }    return 0;}

 

hdu1829 A Bug's Life 基础种类并查集