Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 30 Mar, 2021

Moderate

```
• It is connected
• It has no cycle.
```

```
If n = 5 and if there are 4 edges i.e [ [0, 1], [0, 2], [0, 3], [1, 4]] so the graph formed will look like this:-
```

```
Here this graph is connected and it has no cycle so it is a tree.
```

```
The first line of input contains an integer T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test contains an integer ‘N’ where N is the number of nodes.
The next line of each test case contains an integer ‘M’ where M is the number of edges.
Then the following m lines contain two space separated integers each representing the list of undirected edges.
```

```
For each test case, print "True" if the graph is a valid tree otherwise print "False".
```

```
You don’t have to take input or print anything. This already has been taken care of. Just implement the function.
```

```
1 <= T <= 5
1 <= N <= 10^3
1 <= M <= 10^3
```

For a graph being a tree, we have to check the following things

- Checking how many connected components are present in the graph, It can only be a tree if it has only one connected component
- Checking if it has a cycle or not.

- We will check connected components using Depth-first Search(DFS).
- Start DFS from every unvisited node from 0 till N-1.
- If we start DFS from zero and there is only one connected component, then all the nodes will get visited after completion of this DFS.
- But if there is more than one connected component, then after visiting all the nodes reachable from zero, we will have to encounter and start from other unvisited nodes too.
- Initialize a variable
*count=0*to store the count of connected components. - Iterate i from 0 to N-1, and a boolean array
*visited*to store the status of visited and unvisited nodes.- If
*visited*[i]==false then DFS(i), and increase*count*by 1.

- If
- If
*count*> 1, then it can’t be a tree. - Else we have to check for a cycle.
- For checking the cycle, start DFS from any node let say zero.
- Visit all direct children of 0, and subsequently their children as well.
- We are working with an undirected graph so a cycle is will be present if a node that is already visited in DFS is the direct children of some node we are currently are at.
- If such a case exits our the cycle will be present. And the graph will not be a tree.
- Otherwise, our graph is a tree.

Similar problems

Minimum Swaps To Make Identical Array

Moderate

Posted: 22 Jan, 2022

Find Center of Star Graph

Easy

Posted: 26 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022