Sphere Online Judge

SPOJ Problem Set (classical)

1436. Is it a tree

Problem code: PT07Y

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


Added by:Thanh-Vy Hua
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: ERL JS
Resource:Co-author Amber

hide comments
2013-12-10 15:00:16 Bhavik
kindly check my solution id:10630933
giving WA..don't know why?
2013-11-13 16:31:12 Avaneesh Rastogi
1) The number of nodes should be raised to a million with the same time limit, to reject solutions which apply a sub-optimal approach
2) Weak test cases should be fixed as reported by other coders.
2013-11-05 18:43:58 blc
What are the expected answers for the following graphs?
1 1
1 1

2 2
1 2
1 2

Last edit: 2013-11-05 19:18:10
2013-11-04 12:19:57 Legolas
No need for BFS or DFS, just check if the graph satisfies certain properties (to be exact, 2) and you're good to go! :)
2013-11-01 20:55:54 Sourabh Verma
@admin Please delete Rodrigo's comment
2013-07-26 15:23:05 Ouditchya Sinha
@Viktor Fonic : Properly written code based on bfs / dfs should give correct output for any test case. My AC code gives "NO" for your test case. :)
2013-06-26 09:27:17 Viktor Fonic
Test cases are weak. Here's test case that prints "YES", but should print "NO":
10 8
7 9
9 1
5 1
3 5
5 6
10 4
10 8
3 7
2013-04-03 10:07:34 Tim Lansen
It's test cases are very weak. The biggest tree grows consistently from edge list, no subtree merge needed when using stream analysis. The 1st hack that works is to check that every new link belongs to set of connected nodes.
2013-03-26 09:11:20 kamalesh
my 150th solution!!!!!!
2013-03-06 19:07:29 coding_express
please post some inputs
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.