Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
||||||||||||||
2015-08-22 23:09:42
awesome problem ..learned a lot !!! |
||||||||||||||
2015-08-18 10:56:19 Vivek
if Using DFS, Don't use ADJ Matrix.It would result in O(v^2) time. Go for DFS+ ADJList. With Matrix,got TLE, With List Accepted. |
||||||||||||||
2015-08-12 05:24:18 SangKuan
first i used visited array and got many errors,then is use two hash, colored and merge the edge got ac.no need dfs or bfs, but i think union find is the best way Last edit: 2015-08-12 05:24:51 |
||||||||||||||
2015-08-10 15:48:19 nadavishe
Very week test cases |
||||||||||||||
2015-08-04 01:50:59 Saksham
no need of graph |
||||||||||||||
2015-07-28 13:52:53 harkirat
how weak are the test cases? My solution is completely wrong but got ac! |
||||||||||||||
2015-07-05 18:13:25 Anurag Pasi
@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.. i hope this helps |
||||||||||||||
2015-07-03 14:37:39 Tanmay Kulshrestha
A confusion: If m==n-1 and still it's not a tree, it means there is a cycle in the graph and for that to happen, there should be a totally disconnected node, right, because otherwise total edges will increase. Please help !! Last edit: 2015-07-03 14:38:18 |
||||||||||||||
2015-06-30 13:39:28 Anurag Pasi
Implementation of DFS by Adjacency list+STL 0.00 sec and 3.4Mb :) There are total 3 conditions to check for a tree : 1) connected graph 2) non-cyclic or acyclic 3) n-1==m but actually u hav to check only 2 conditions if u think :) Last edit: 2015-06-30 13:41:24 |
||||||||||||||
2015-06-29 19:36:41 gamer496
@Sukeesh YES |