这个题目很有意思啊,有一些bug生物(肯定是程序员养的),有人观察他们的生活习惯,观察他们之间是否有同性恋关系,比如ab发生关系,bc发生关系,ab发生关系。。。产生了同性恋了,你需要判断一下这种关系是不是存在。
分析,这个跟食物链没什么区别,而且条件还少了不少,规定同性关系是0, 异性关系是1
//////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include<algorithm>
using namespace std; const int maxn = ; int f[maxn], relation[maxn];//0表示同性,1表示异性 int Find(int x)
{
int k = f[x];
if(f[x] != x)
{
f[x] = Find(f[x]);
relation[x] = (relation[x]+relation[k])%;
} return f[x];
} int main()
{
int T, t=; scanf("%d", &T); while(T--)
{
int i, N, M, u, v, ru, rv, ok = ; scanf("%d%d", &N, &M); for(i=; i<=N; i++)
f[i] = i, relation[i] = ; for(i=; i<M; i++)
{
scanf("%d%d", &u, &v); if(ok)continue; ru = Find(u), rv = Find(v); if(ru == rv && (relation[v]+)% != relation[u])
ok = ;
else if(ru != rv)
{
f[ru] = rv;
relation[ru] = (-relation[u]+relation[v])%;
}
} if(t != )printf("\n");
printf("Scenario #%d:\n", t++);
if(ok)printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
} return ; }