Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

刚学完食物链... 自己理解着做的

Posted by 461807914 at 2014-02-17 21:05:59 on Problem 2492
#include<iostream>
using namespace std;
int father[2005];
int rela[2005];
int flag;
int N,cas;//虫子数,案例数
int Find(int x)
{
	int px;
	if(x==father[x]) return x;
	px=Find(father[x]);
	rela[x]=(rela[x]+rela[father[x]])%2;
	return father[x]=px;
}
void Union(int x,int y)//0表示同性,1表示异性
{
	int px,py;
	px=Find(x);
	py=Find(y);
	if(px==py)
	{
		if(rela[x]==rela[y])//与根节点的关系相同,那这个虫子必然同性
			flag=1;
		return;
	}
	else//不同就连上
	{
		father[px]=py;
		rela[px]=(rela[y]-1-rela[x]+2)%2;
	}
	return;
}
void ini()
{
	int i;
	for(i=1;i<=N;i++)
	{
		father[i]=i;
		rela[i]=0;//自己和自己肯定是同性
	}
	flag=0;
}
int main()
{
	int t,i,j=1;
	int x,y;//两个虫子
	int tem;
	scanf("%d",&t);
	while(t--)
	{
		tem=0;
		scanf("%d%d",&N,&cas);
		ini();
		for(i=1;i<=cas;i++)
		{
			scanf("%d%d",&x,&y);
			Union(x,y);
			if(flag==1)
			{
				tem=1;
			}
		}
		if(tem)
			printf("Scenario #%d:\nSuspicious bugs found!\n\n",j++);
		else
			printf("Scenario #%d:\nNo suspicious bugs found!\n\n",j++);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator