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
|
coder_shishir:
2015-08-22 23:09:42
awesome problem ..learned a lot !!! |
|
Vivek:
2015-08-18 10:56:19
if Using DFS, Don't use ADJ Matrix.It would result in O(v^2) time.
|
|
SangKuan:
2015-08-12 05:24:18
first i used visited array and got many errors,then is use two hash, colored and merge the edge got ac.no need
|
|
nadavishe:
2015-08-10 15:48:19
Very week test cases |
|
Saksham :
2015-08-04 01:50:59
no need of graph |
|
harkirat:
2015-07-28 13:52:53
how weak are the test cases?
|
|
Anurag Pasi:
2015-07-05 18:13:25
@Tanmay Kulshrestha I partially agree with u, when m==n-1 and still not a tree i.e it is cyclic , but i dont think there will b a totally disconnected node mayb there or mayb not u cant say..
|
|
Tanmay Kulshrestha:
2015-07-03 14:37:39
A confusion:
|
|
|
Anurag Pasi:
2015-06-30 13:39:28
Implementation of DFS by Adjacency list+STL 0.00 sec and 3.4Mb :)
|
|
gamer496:
2015-06-29 19:36:41
@Sukeesh YES |
| 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