PT07Y - Is it a tree

You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.


The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph (0 < N <= 10000, 0 <= M <= 20000). Next M lines contain M edges of that graph --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).


Print YES if the given graph is a tree, otherwise print NO.


3 2
1 2
2 3


hide comments
karandeep09: 2019-12-30 16:38:25

if n==no. of times dfs runs && n==m+1

r15habhgup11: 2019-11-05 11:46:00

Can someone plzz tell me answer of this case and why
6 5
1 4
2 4
3 4
5 4
5 6

invincibel: 2019-09-23 08:40:58

use union-find much better for this problem

mriow: 2019-08-21 07:55:05


Any connected graph G with n vertices and (n-1) edges is a tree (No need to search for cycles, only connection)

Last edit: 2019-08-21 07:56:17
ashishgh1997: 2019-08-17 08:05:37

The tree may not be a binary tree. A node may have more than 3 childs

veerendrasd_9: 2019-07-20 19:35:16

AC only if one considers it as directed Graph.

Last edit: 2019-07-20 19:36:10
an09mous: 2019-07-03 13:47:50

For a graph to be a tree, there must be no cycles and not any isolated vertices. So number of edges will always be n-1. If edges are exactly equal to n-1, then we just have to check if there is a cycle or not.

Last edit: 2019-07-03 13:48:05
gyanendra371: 2019-06-22 15:19:05

check for cycle and if not found then check all nodes are visited .

itsmysyntax: 2019-06-06 20:10:39

@itsshubham_m12 clearly its given in question that its undirected graph

nishit5: 2019-05-29 11:33:31

use in one go

Added by:Thanh-Vy Hua
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Co-author Amber