首页 > 代码库 > POJ 1308 Is It A Tree?

POJ 1308 Is It A Tree?

注:这道题思路很乱,先记下,日后理清

题意:给出一些节点,判断这些节点构成的是不是一棵树

思路:感觉很简单,但是思路又很乱,当时想的判断条件是:

1.入度不能大于1(树根为0,其他节点为1)

2.所有节点必须在一棵树中(判断所有节点是否在一棵树中)

3.在节点相连的时候,不能是同一棵树中的节点(否则会出现环或者入度为2的情况)

#include<iostream>#include<cstring>#include<stdio.h>using namespace std;int set[50000];int a[50000];int rootnum[50000];int set_find(int d){	if(set[d]<0)		return d;	return set[d]=set_find(set[d]);//这里不要忘了return(有的编译器可能是自动加上return,在vc中不会报错,运行结果也正确)}void join(int x,int y){	x=set_find(x);	y=set_find(y);	set[x]=y;}int main(){	int i;	int m;	int mcase=0;	while(1)	{	    bool ok=true;		memset(set,-1,sizeof(set));		memset(rootnum,0,sizeof(rootnum));		i=0;		m=0;		scanf("%d%d",&a[i],&a[i+1]);		m++;m++;		mcase++;		if(a[i]<0 &&a[i+1]<0) break;		if(a[i]!=0 &&a[i+1]!=0)		{			if(set_find(a[i+1])!=set_find(a[i]))//  3.  连得时候不能是同一棵树中的两个节点相连(排除自己连自己)				join(a[i+1],a[i]);            else ok=false;			rootnum[a[i+1]]++;			i++;i++;			while(scanf("%d%d",&a[i],&a[i+1]))			{				if(a[i]==0 &&a[i+1]==0)break;				m++;m++;				if(set_find(a[i])!=set_find(a[i+1]))//  3. 连得时候不能是同一棵树中的两个节点相连				{					join(a[i+1],a[i]);				}				else ok=false;				rootnum[a[i+1]]++;				i++;i++;			}		}		int root=set_find(a[0]);		for(i=0;i<m;i++)		{			if(rootnum[i]>1||set_find(a[i])!=root)//  1.入度不能大于1 , 2.所有节点必须在一棵树中			{				ok=false;				break;			}		}		if(ok)			printf("Case %d is a tree.\n",mcase);		else			printf("Case %d is not a tree.\n",mcase);	}	return 0;}