PT07Y - Is it a tree
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
hide comments
|
Shubham Sharma:
2014-01-21 16:41:12
Very Weak test cases ! |
|
adze:
2014-01-10 23:52:01
@Paul Draper
|
|
Bhavik:
2013-12-10 15:00:16
kindly check my solution id:10630933
|
|
Avaneesh Rastogi:
2013-11-13 16:31:12
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
|
|
blc:
2013-11-05 18:43:58
What are the expected answers for the following graphs?
|
|
Sourabh Verma:
2013-11-01 20:55:54
@admin Please delete Rodrigo's comment |
|
Ouditchya Sinha:
2013-07-26 15:23:05
@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. :) |
|
Viktor Fonic:
2013-06-26 09:27:17
Test cases are weak. Here's test case that prints "YES", but should print "NO":
|
|
Tim Lansen:
2013-04-03 10:07:34
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. |
|
kamalesh:
2013-03-26 09:11:20
my 150th solution!!!!!! |
| Added by: | Thanh-Vy Hua |
| Date: | 2007-03-28 |
| Time limit: | 0.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO |
| Resource: | Co-author Amber |
RSS