Last Updated: 5 Feb, 2021

Is Graph Tree?

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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.

Solve now

02 Approach

We will use the same idea that we used in the previous approach. We will look for cycles in the graph. This time we will use bfs to check cycles. We will maintain parents of all nodes in an array and if we can find a back-edge then it will tell us that the graph contains a cycle. Also After running bfs if there remains an unvisited node then it shows the graph is disconnected. If our graph is connected and doesn’t contain a cycle then it will be a tree.

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 and initialize all elements of it with zero.
Create an adjacency list graph using the edges array given in the problemCall BFS function with starting node as 0 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 BFS function :

bool bfs (graph, visited) :

Declare an array to store parents of all nodes say ‘parent’.
Declare an empty queue, say ‘q’ and push 0 to it.
Run a loop until the queue is not empty.
Pop front element from the queue. Say ‘curNode’.
Visit all neighbours of ‘curNode’
If we have visited the neighbour of ‘curNode’ and its value is not equal to the parent of ‘curNode’ then return true as we have found a back-edge.
If we have not visited this neighbour then set the parent of the neighbour node as ‘curNode’.
Mark neighbour node visited as true and push it in the queue.
After visiting all nodes return false as we are not able to find a cycle in the graph.

Solve now