poj 1308

注意的情况比较多，尤其是空树这一种

#include <iostream>
#include <stdlib.h>
using namespace std;
const int maxn=100;
struct node
{
	int s,f;
	node* next;
};//在此数据结构采用链表，方便后续遍历算法
int indexNode[maxn];//用于构造索引的数组
int v[maxn];
node *head;
int totNode;//节点的总数
void visitNode(int temNode)
{
	node* p=head->next;
	v[temNode]++;
	while(p!=NULL)
	{
		if(p->s==temNode) visitNode(p->f);
		p=p->next;
	}
}
int getLoc(int n)//构造索引。因为输入的节点数据不是连续的，构造索引方便后续的查找确定
{
	int i;
	for(i=0;i<totNode;i++)
	{
		if(indexNode[i]==n) return i;
	}
	indexNode[totNode++]=n;
	return totNode-1;
}
bool isATree()
{
	if(totNode==0) return true;
	int i;
	node *p;
	int rnum=0;
	int rootIndex=-1;
	for(i=0;i<totNode;i++)
	{
		p=head->next;
		int m=0;
		while(p!=NULL)
		{
			if(p->f==i) m++;
			p=p->next;
		}
		if(m==0)
		{
			rnum++;
			rootIndex=i;
		}
		if(m>1) return false;//有多个节点指向此节点
	}
	if(rnum!=1) return false;//无根节点或有多个根节点
	memset(v,0,sizeof(v));
	visitNode(rootIndex);//刚开始以为这一步是多余的以为和有多个节点指向一个节点是一种情况，但还是忽略 一种情况就是树加环这一情况
	for(i=0;i<totNode;i++)
	{
		if(v[i]!=1) return false;
	}
	return true;
}
int main()
{
	int s,f;
	int t=0;
	while(cin>>s>>f)
	{
		if(s==-1&&f==-1) break;
		totNode=0;
		t++;
		head=new node;
		head->next=NULL;
		node *p;
		while(1)
		{
			if(s==0&&f==0) break;
			p=new node;
			p->s=getLoc(s);
			p->f=getLoc(f);
			p->next=head->next;
			head->next=p;
			cin>>s>>f;
		}
		bool flag=isATree();
		if(flag)
			cout<<"Case "<<t<<" is a tree."<<endl;
		else
			cout<<"Case "<<t<<" is not a tree."<<endl;
		p=head;
		node *r;
		while(p!=NULL)
		{
			r=p->next;
			delete p;
			p=r;
		}
	}
	return 0;
}