poj 2492(关系并查集) 同性恋

时间:2024-06-23 11:36:38

题目;http://poj.org/problem?id=2492

卧槽很前卫的题意啊,感觉节操都碎了,

t组测试数据,然后n,m,n条虫子,然后m行,每行两个数代表a和b有性行为(默认既然能这样就代表两者是异性),最后问的是 有没有同性恋, 比如a,b  b,c  a,c

第一组可以得到a和b是异性,第二组可以得到b和c是异性,因为只有两种性别,所以可以得出a和c一定是同性,但是第三组有表明a和c有性行为,赤裸裸的同性恋

所以输出 Suspicious bugs found!

和食物链哪题差不多,也是关系型并查集,这里的关系只有0和1两种,相等即为同性,不等就是异性

 #include<cstdio>
using namespace std;
int father[],ran[];
void give(int n)
{
for (int i=;i<=n;i++)
{
father[i]=i;
ran[i]=;
}
}
int _find(int x)
{
if (x==father[x]) return father[x];
int t=_find(father[x]);
ran[x]=(ran[x]+ran[father[x]]+)%;
father[x]=t;
return father[x];
}
int main()
{
int n,m,t,ans,x,y,flag;
scanf("%d",&t); ans=;
while (t--)
{
scanf("%d %d",&n,&m);
give(n);
flag=;
while (m--)
{
scanf("%d %d",&x,&y);
int sx=_find(x);
int sy=_find(y);
if (sx!=sy)
{
father[sx]=sy;
ran[sx]=(ran[y]-ran[x]++)%;
}
else
{
if (((ran[x]-ran[y]+)%)!=)
flag=;
}
}
printf("Scenario #%d:\n",ans++);
if (flag==) printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
printf("\n");
} return ;
}