1308.cpp

acm-pku-1308 Is It A Tree?

#include<iostream.h>

struct treelink
{
	int to;
	int from;
	treelink * next;
} *Fhead,*Fend;



void link(int to,int from)
{
	treelink *temp=new treelink;
	temp->to=to;
	temp->from=from;
	Fend->next=temp;
	Fend=temp;
	temp->next=NULL;
}

int searchto(treelink *hp,int to)
{
	treelink *temp;
	temp=hp->next;
	while(temp) 
	{
		if(temp->to==to) return 0;
		temp=temp->next;
	}
	return 1;
}

int searchfrom(treelink *hp,int to,int from)
{
	treelink *temp;
	temp=hp->next;
	while(temp) 
	{
		
		if(temp->to==from)
		{
			
			from=temp->from;
			if(from==to)  return 0; 
			temp=hp->next;
		}
		else temp=temp->next;
	}
	return 1;
}

void cuttree(int from)
{
	int tempfrom;
	treelink *temp;
	temp=Fhead;
	while(temp->next) 
	{
		if(temp->next->from==from)
		{
			tempfrom=temp->next->to;
			cuttree(tempfrom);
			temp->next=temp->next->next;
			temp=Fhead;
		}
		else temp=temp->next;
	}
}

void getfrom()
{
	treelink *temp;
	int from;
	temp=Fhead->next;
	if(temp==NULL) return;
	from=temp->from;
	while(temp) 
	{
		if(temp->to==from)
		{
			from=temp->from;
			temp=Fhead->next;
		}
		else temp=temp->next;
	}
	cuttree(from);
}



void move(int *i)
{
	int F,N;
	while(1)
	{
		cin>>F>>N;
		if(F==0&&N==0) 
		{
			*i=*i+1;
			cout<<"Case "<<(*i)<<" is not a tree."<<endl;
			break;
		}
	}
}



int main()
{
	int F,N,i=0;
	Fhead=new treelink;
	while(1)
	{
		cin>>F>>N;
		if(F<0&&N<0) break;
		Fend=Fhead; Fend->next=NULL;
		while(1)
		{
		    if(F==0&&N==0) 
			{
				getfrom();
			    i++;
			    if(Fhead->next==NULL) cout<<"Case "<<i<<" is a tree."<<endl;
			    else cout<<"Case "<<i<<" is not a tree."<<endl;
				break;
			}
		    else
			{
				if(N==F)  { move(&i); break;}
				else if(searchto(Fhead,N)==0)  { move(&i); break; }
			    else if(searchfrom(Fhead,N,F)==0) { move(&i); break; }
			    else link(N,F);
			}
			cin>>F>>N;
		}
	}
	return 0;
}