615 - Is It A Tree?

Difficulty : medium

Solution Description :

Graph problem

Here is maximum 100 pair in a input set. So, you can store parent and child in two array. parent[101], child[101]. Do not use adjacency matrix because value of a node is not small. 

Suppose a pair (x,y) if x==y then it is not a tree. Example 1 1   0 0. it is not a tree.
If any child have more than 1 parent then it is not a tree. Example 1 2   3 2   0 0. Here node 2 have more than 1 parent so it is not a tree.
Find the main root. Main root is a node which has no parent. Example 1 2   1 3   3 4   0 0. Here main root is 1 
Run any graph traversal algorithm where start node main root.
If all other node visited from start node then it is a tree. otherwise it is not a tree.

For traversal you can use the recursion method
DFS(int root)
----for i=0 to N //Here N=number of pair
-------if(parent[i]==root) DFS(child[i])

Remember if a input graph is empty then it is a tree. Example 0 0. It is a tree.