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

knir0103: 2019-03-05 02:51:04

test cases 've been fixed to be undirected

Last edit: 2019-03-05 02:51:18
akashbhalotia: 2019-01-20 11:59:39

AC in java. Simple DSU. Only create DSU if M=N-1, else you will get TLE.

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