学步园

题意：给出一些仰慕的关系，问有没有同性恋。

思路：给图染色，判断是不是二分图就可以。

#include<stdio.h>
#include<string.h>
const int N=2100;
int head[N],color[N],num,flag;
struct edge
{
	int st,ed,next;
}e[N*1000];
void addedge(int x,int y)
{
	e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;
	e[num].st=y;e[num].ed=x;e[num].next=head[y];head[y]=num++;
}
void judge(int u)
{
	int i,v;
	for(i=head[u];i!=-1;i=e[i].next)
	{
		v=e[i].ed;
		if(color[v]==-1)
		{
			color[v]=(color[u]^1);
			judge(v);
		}
		else if(color[v]==color[u])
		{flag=1;return ;}
	}
	return ;
}
int main()
{
	int i,x,y,t,op=1,n,m;
	scanf("%d",&t);
	while(t--)
	{
		memset(head,-1,sizeof(head));
		num=0;
		memset(color,-1,sizeof(color));
		scanf("%d%d",&n,&m);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			addedge(x,y);
		}
		printf("Scenario #%d:\n",op++);
		flag=0;
		for(i=1;i<=n;i++)
		{
			if(color[i]==-1)
			{		
				color[i]=0;judge(i);
				if(flag==1)break;
			}
		}
		if(i>n)printf("No suspicious bugs found!\n\n");
		else printf("Suspicious bugs found!\n\n");
	}
	return 0;
}