Is It A Tree?

Moderate

0/80

Average time to solve is 20m

Contributed by

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

Console