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

Re:2 1 3 1 4 1 是不是树???没有方向??

Posted by fff123 at 2011-04-07 15:46:13 on Problem 1308
In Reply To:2 1 3 1 4 1 是不是树???没有方向?? Posted by:fff123 at 2011-04-07 15:33:47
> 谁告诉我啊。。。。2 1 3 1 4 1  是不是树???????????
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1000
int father[N],node[N];
void init(void)
{
	int i;
	for(i=0;i<N;i++)
	{
		father[i]=i;
		node[i]=0;//标记出现的节点
	}
	return ;
}
int getfather(int x)
{
	if(x!=father[x])
	{
		father[x]=getfather(father[x]);
	}
	return father[x];
}
void uniontree(int x,int y)
{
	int p, q;
	p=getfather(x);
	q=getfather(y);
	if(q==p)
		return ;
	father[p]=q;
	return ;
}
int main(void)
{
	int a,b,i,t=1,tag,root;
	while(1)
	{
		scanf("%d%d",&a,&b);
		if(a==-1&&b==-1)
			break;
		if(a==0&&b==0)//null tree
		{
			printf("Case %d is a tree.\n",t++);
			continue;
		}
		init();
		node[a]=node[b]=1;
		root=a;
		tag=1;
			if(a==b)//指向自己的不是树
				tag=0;
			else
				uniontree(a,b);
		while(scanf("%d%d",&a,&b)&&!(a==0&&b==0))
		{
			if(getfather(a)==getfather(b))//祖先相同,肯定有环
				tag=0;
			uniontree(a,b);
			node[a]=node[b]=1;

		}
		if(tag==1)
		{
			root=getfather(root);
		for(i=0;i<N;i++)
		{
			if(node[i]&&getfather(i)!=root)//祖先必须相同,否则就是森林
				tag=0;
		}
		}
		printf("Case %d is ",t++);
		if(tag==1)
			printf("a tree.\n");
		else
			printf("not a tree.\n");
	}
	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