New update is available. Click here to update.

Problem

Submissions

Solution

New

Discuss

Is It A Tree?

Contributed by

Shivam Kumar Singh

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 20 mins

Success Rate 75 %

21 upvotes

Problem Statement

Suggest Edit

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.

Auto

Console

Graphs Notes

Is it a Tree?

M-Coloring Problem

Count nodes within K-distance

Shortest path in an unweighted graph

Fire in the cells

Strongly Connected Components (Tarjan’s Algorithm)

Minimum Spanning Tree

Dijkstra’s shortest path

Snake and Ladder

Alien dictionary