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
lisbecg: 2016-04-15 03:22:32

Did you guys build the graph in order to do DFS?

sharif ullah: 2016-03-12 12:31:25

just use union find check if there is a loop!

vimal: 2016-03-06 17:12:11

accepted on codechef... WA here... :D
UPDATE : solved. hint:what are 3 important prop. of a tree ?

Last edit: 2016-03-06 17:24:21
Neeraj Singh Aithani: 2016-02-16 16:56:15

Actually Test Cases are very weak my solution for
4 3
4 2
4 3
2 1
is NO.But it is AC

dkumarsingh: 2016-01-22 21:14:52

i am using matrix to represent it's structure as a graph but getting sigsev error

Aqib Ahmed J: 2016-01-16 06:00:11

Tree doesn't have loops ! Cost me one WA :|

RADHE SHYAM LODHI: 2016-01-12 05:10:29

AC union set 0.00 ..

dokz: 2016-01-06 06:33:31

Got AC. Just run the single DFS:
1) Check for loops - grey (visited, but not left) vertex found - loop, output "NO"
2) Check for single connected component - after DFS all vertices should be colored black (visited and left)

Deepak : 2015-12-30 12:34:06

thanks @rahul for your hint

AASHISH KUMAR: 2015-12-25 10:01:02

AC in one go :) yeyii

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