Is Graph Tree?

Easy
0/40
Average time to solve is 15m
profile
Contributed by
22 upvotes
Asked in companies
WalmartRazorpay

Problem statement

Ben Tennyson recently joined Coding Ninjas to become better at competitive programming.

To check whether Ben is seriously studying in Coding Ninjas or not, Gwen challenged Ben to solve a problem and Ben accepts the challenge of Gwen.

Gwen gives Ben an undirected graph of ‘N’ nodes numbered from 0 to ‘N - 1’ having ‘M’ edges. The task of Ben is to check whether the graph given by Gwen is a tree or not.

As Ben is busy fighting with Evil doers so he asked you to solve this problem.

Note : 
There are no parallel edges and self-loops in the graph given by Gwen.

A tree is a connected graph having no cycles.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’. Here ‘N’ denotes the total number of nodes and ‘M’ denotes the total number of edges in the graph given by Gwen.

The next ‘M’ lines contain two space-separated integers ‘U’ and ‘V’. Here ‘U’ and ‘V’ represent the nodes that share an edge between them.
Output Format : 
For each test case, print 1 if the graph given by Gwen is a tree, else you need to print 0.

The output of each test case will be printed in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 5000
1 <= M <= min(5000, N*(N-1)/2)
1 <= U, V<= N - 1
Sample Input 1:
2
7 6
0 1
0 4
1 2
1 3
4 5
4 6
3 3
0 1
0 2
1 2
Sample Output 1:
1 
0
Explanation For Sample Input 1:
Test Case 1 :  
The given graph is shown below.

1 

The above graph is a connected graph with no cycles. Hence this graph is a tree. So we need to print 1.

Test Case 2 : 
The given graph is shown below.

1

Above graph is a connected graph but it contains a cycle : 0 -> 1 -> 2 .Hence this graph is not a tree. So we need to print 0.
Sample Input 2:
2
4 3
0 1
0 2
3 2
5 5
0 1
0 3
2 1
2 3
1 4
Sample Output 2:
1
0
Hint

Use the fact that Tree is a connected graph having no cycle.

Approaches (2)
DFS Approach

The idea here is to check to use the fact that Tree is a connected graph having no cycles. For a graph to be connected it must have only one connected component. We can check both of these conditions using dfs.

 

We will run dfs starting from node zero and if all nodes are not visited then it means that we cannot reach a node from node number zero. So it shows that the graph is disconnected.

 

To check for the cycle we need to check whether the given graph contains a back-edge or not. If the graph doesn’t contain a back edge then it means it does not contain a cycle. 

 

Consider the below example for better understanding.  

E:\coding ninjas\Phase 2\Problem 5 - Check Tree\images\back edge.jpg

 

In the above figure, we start dfs from node 0 and visit node 1, 2, 6 respectively (visited nodes are marked red). After reaching 6 we have found that node 6 has one more parent other than 2 which is 3. So the edge between 3 and 6 is back-edge. It is telling us that there is also another path through which we can reach 6 other than our current dfs path that is 0-> 3 -> 6. So we can go back to start node 0 from 6 using path 6  -> 3 -> 0. So it will create a cycle of 0->1->2->6->3->0. 

 

Algorithm:

 

  • Declare the following things:
  • A variable ‘answer’ to check whether the given graph is a tree or not and initialize it with true.
  • A 2-D array/list ‘graph’ to create the graph using the given number of nodes and edges.
  • An array ‘visited’ to keep track of visited elements, initialize all elements of it with zero.
  • Build an adjacency list using the edges array given in the problem.
  • Call the DFS function to check whether a graph contains a cycle or not. If the graph contains a cycle then set ‘answer’ as false.
  • Run a loop from node = 0 to ‘N – 1’.
  • If ‘visited[node]’  is equal to false, then set ‘answer’ as 0 as it shows that the graph has multiple connected components.
  • Finally, return the ‘answer’.

 

Description of DFS function :

 

bool dfs (curNode, parent, graph, visited) :    

 

  • Mark ‘visited[curNode]’ = true.
  • Visit all neighbours of ‘curNode’.
  • If a neighbour of ‘curNode’ is not visited then recursively call dfs to visit this node and if this recursive call returns true then return true else continue to check the next neighbour.
  • Else if this neighbour node is not equal to the parent then return true. As this shows there is another path through which we can reach ‘curNode’ and thus it confirms that the graph has a cycle.
  • After visiting all neighbours return false as we are not able to find a cycle in the graph.
Time Complexity

O(N + M), where ‘N’ is the total number of nodes and ‘M’ is the total number of edges in the graph.

 

Here, building a graph takes O(M) time as we need to add ‘M’ edges to the graph. Also, our dfs function takes O(N) time as we need to visit all nodes in the worst case. 

 

Hence, the overall time complexity will be O(N) + O(M) = O(N + M).

Space Complexity

O(N + M), where ‘N’ is the total number of nodes and ‘M’ is the total number of edges in the graph.

 

We are using a visited array that takes O(N) space. Adjacency list takes O(M) space as we need to insert ‘M’ edges to the list. Also, our dfs function requires O(N) space in recursive calls. 

Hence, the overall space complexity will be O(N) + O(M)  + O(N) = O(N + M).

Code Solution
(100% EXP penalty)
Is Graph Tree?
Full screen
Console