注：这道题思路很乱，先记下，日后理清

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

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

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;}