Problem

Submissions

Hints & solutions

Discuss

Is It A Tree?

Moderate

0/80

Average time to solve is 20m

Contributed by

31 upvotes

Asked in companies

Problem statement

Given a graph with 'V' vertices numbered from 0 to 'V' - 1 and 'E' edges. Determine if it is a tree or not?

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains two integers 'E' and 'V', separated by a single space. They denote the total number of edges and vertices respectively. 

From the second line onwards, the next 'V' lines represent an edge between the two vertices.

Every edge is represented by two vertices(u, v) that share an edge between them. The values of the vertices would again be separated by a single space.

Output Format :

The only line of output prints 'True' if the given graph is a tree, otherwise print 'False'.

Constraints :

1 < 'V' <= 10^5
0 <= 'E' <= min(10^5, V*(V-1)/2)
0 <= u, v <= V-1

Time Limit: 1 sec

Sample Input 1:

3 2
0 1
1 2

Sample Output 1:

True

Explanation of Sample Input 1:

We clearly can see that it is a tree since it satisfies the property of a tree.

Sample Input 2:

Sample Output 2:

False

Explanation of Sample Input 2:

As we can see that it is not a tree since it doesn't satisfy the property of a tree.

Hint 1

Hint 2

A graph is a tree if it is acyclic and connected.

Approaches (2)

Approach 1

Approach 2

DFS

A graph is a tree if the following two conditions are satisfied:

There are no cycles present in the graph
The graph is connected

Algorithm for checking cycle in Graph.

Create the graph using the given number of edges and vertices.
Run a DFS from starting from any vertex along with the track of the parent (initially, parent of every vertex is -1)
Recur for all the vertices adjacent to the current vertex.
If an adjacent vertex is not visited, then recur for that adjacent vertex.
If an adjacent vertex is visited and it is not the parent of the current vertex, then there is a cycle.

Algorithm for checking whether the graph is connected or not
1. After DFS, check if all the vertex is not visited or not.
2. If it is visited then it is connected.

Time Complexity

O(V+E), where V is the number of vertices and E is the number of Edges.

Through DFS, we traverse every vertex at max once and every edge at max once. Therefore the net time complexity is O(V+E).