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.

Input

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

Output

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

Example

Input:
3 2
1 2
2 3

Output:
YES

Added by:	Thanh-Vy Hua
Date:	2007-03-28
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-04-03 12: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 10:11:20 kamalesh
my 150th solution!!!!!!

2013-03-06 20:07:29 rowdy
please post some inputs

2013-01-11 10:42:15 Aayush

Last edit: 2013-01-11 10:56:51

2012-11-21 04:31:53 Paul Draper
Weak test cases. Trees are always built in order; i.e. no
4 3
1 2
3 4
1 3

2012-11-14 20:51:05 kailash
Can I get some test cases.
My code is working for my inputs but spoj is showing WA.

2012-09-20 00:15:01 Ashwin Menon
Are the nodes contiguous?

1, 2, 3 ... N?

2012-09-12 02:32:52 Rodrigo Salazar
If you're having difficulty and not sure if you're on the right track, check out this explanation:

http://www.swageroo.com/wordpress/spoj-problem-1436-is-it-a-tree-pt07y/

2012-08-26 03:13:12 KEVALSAHU
simple problem guys :)

Last edit: 2012-08-26 03:14:34

2012-07-05 06:29:30 Simón Murillo Gómez
DFS and a little detail can solve the problem.

BFS goes better with the problem nature :)

Last edit: 2012-08-02 01:23:02