615

The problem is to finding a tree from a given graph.The main challenge is that the value of the node is not provided.

So adjacency matrix can not be used to solve the problem.

To define a tree for a directed graph : total edges = total vertices -1;root can not be more than one, each node must have one in coming edge (except root has 0),using dfs/bfs all the node can be traversed from root(each node has a unique path from tree.)

#include <cstdio>
#include <iostream>

using namespace std;

struct Node{
	int number;
	Node *next;
};

struct Edge{
	int from,to;
	Edge(int f,int t);
	Edge *nextEdge;
};

Node *nodeList=0;
Edge *edgeList=0;
int root;

void init()
{
	Node *p=nodeList,*q;
	while(p)
	{
		q=p;
		p=p->next;
		delete(q);
	}
	nodeList = new Node;
	nodeList->number=-100;
	nodeList->next=0;
}
int GetNodeIndex(int num)
{
	Node *tmpNode=nodeList;
	int idx=0;
	while(tmpNode->next)
	{
		tmpNode = tmpNode->next;
		if(tmpNode->number==num)
		return idx;
		idx++;
	}
	tmpNode->next = new Node;
	tmpNode = tmpNode->next;
	tmpNode->number = num;
	tmpNode->next=0;
	return idx;
}
Edge::Edge(int a,int b)
{
	int fr = GetNodeIndex(a);
	int t = GetNodeIndex(b);
	from = fr;
	to = t;
}

int CountNode()
{
	Node *p=nodeList->next;
	int c=0;
	while(p)
	{
		p=p->next;
		c+=1;
	}
	return c;
}

int findIndegree(int nodeIndex)
{
	Edge *p =edgeList;
	int cnt=0;
	while(p)
	{
		if(p->to==nodeIndex)
			cnt+=1;
		p=p->nextEdge;
	}
	return cnt;
}

void dfs(bool visited[],int nodeIdx)
{
	visited[nodeIdx]=1;
	Edge *p=edgeList;
	while(p)
	{
		if(p->from==nodeIdx)
			dfs(visited,p->to);
		p=p->nextEdge;
	}
}
bool isTree()
{
	int nodeCount = CountNode();
	int tmp;
	root = -1;
	if(nodeCount==0)//empty tree
	return 1;
	//check for the root (=node having 0 indegree) and it is single in the graph
	//also check for the node have more than one parents
	for(int i=0;i<nodeCount;i++)
	{
		tmp = findIndegree(i);
		if(tmp>1)
		{
			return 0;
		}
		if(tmp==0)
		{
			if(root==-1)
				root=i;
			else
			{
				return 0;
			}
		}
	}
	if(root==-1)
	{
		return 0;
	}
	bool *visited= new bool[nodeCount];
	for(int i=0;i<nodeCount;i++)
		visited[i]=false;

	dfs(visited,root);
	for(int i=0;i<nodeCount;i++)
		if(!visited[i])
		{
			delete(visited);
			return 0;
		}

	delete(visited);
	return 1;
}
int main()
{
	int from,to;
	int kase=1;
	while(scanf("%d%d",&from,&to),from>=0,to>=0)
	{
		init();
		edgeList=0;
		while(from||to)
		{
			Edge *e =  new Edge(from,to);
			e->nextEdge = edgeList;
			edgeList = e;
			scanf("%d%d",&from,&to);
		}
		printf("Case %d is %sa tree.\n",kase++,isTree()?"":"not ");
		while(edgeList)
		{
			Edge *dEdge=edgeList;
			edgeList=edgeList->nextEdge;
			delete(dEdge);
		}
	}
	return 0;
}