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

klmo: 2019-04-24 10:37:57

To check if connected better use optimized DSU than DFS.

itsshubham_m12: 2019-04-22 17:12:34

Is the graph directed or not??

ll14: 2019-03-15 00:05:27

If you're using Java and has the TLE, please never use Scanner instead of BufferReader

mynk322: 2019-03-13 10:10:24

Tree is undirected!
Only check for 2 cases :-
1) e=n-1
2) Only 1 conected component!

haiderbaig: 2019-03-06 10:24:51

Very good introduction to DFS.
2 points to keep in mind:
* a tree has no cycles
* a tree has no isolated node

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