poj 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两种,相等即为同性,不等就是异性

 1 #include<cstdio>
 2 using namespace std;
 3 int father[2001],ran[2001];
 4 void give(int n)
 5 {
 6     for (int i=1;i<=n;i++)
 7     {
 8         father[i]=i;
 9         ran[i]=0;
10     }
11 }
12 int _find(int x)
13 {
14     if (x==father[x]) return father[x];
15     int t=_find(father[x]);
16     ran[x]=(ran[x]+ran[father[x]]+2)%2;
17     father[x]=t;
18     return father[x];
19 }
20 int main()
21 {
22     int n,m,t,ans,x,y,flag;
23     scanf("%d",&t);
24 
25         ans=1;
26         while (t--)
27         {
28             scanf("%d %d",&n,&m);
29             give(n);
30             flag=0;
31             while (m--)
32             {
33                 scanf("%d %d",&x,&y);
34                 int sx=_find(x);
35                 int sy=_find(y);
36                 if (sx!=sy)
37                 {
38                      father[sx]=sy;
39                      ran[sx]=(ran[y]-ran[x]+2+1)%2;
40                 }
41                 else
42                 {
43                     if (((ran[x]-ran[y]+2)%2)!=1)
44                         flag=1;
45                 }
46             }
47             printf("Scenario #%d:
",ans++);
48             if (flag==1) printf("Suspicious bugs found!
");
49             else printf("No suspicious bugs found!
");
50             printf("
");
51         }
52 
53     return 0;
54 }