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
|
||||||||||||||
2016-08-07 13:53:11
Do NOT use spoj toolkit for this one! |
||||||||||||||
2016-07-26 05:46:46
I used union-find tree and I got 0.00 sec! |
||||||||||||||
2016-07-12 13:58:54
I guess the test cases are weak.My naive solution also got accepted. |
||||||||||||||
2016-07-05 13:57:08 Murad Al Wajed
nice graph problem for biggener |
||||||||||||||
2016-07-02 22:36:02 geeta
Easy!!! did using BFS!!! |
||||||||||||||
2016-06-28 20:26:21 KD
DSU rocks!!!!! |
||||||||||||||
2016-06-22 11:19:46
tree should have edges n-1 use union find algo fo detecting cycle. |
||||||||||||||
2016-06-10 18:18:03
HINT : A graph is a cycle if it no. of connected components=1 and edges = nodes-1 Source : https://en.wikipedia.org/wiki/Tree_%28graph_theory%29 |
||||||||||||||
2016-06-08 09:33:08
My first in graph theory!!..AC in one go!! Thanx @dokz for your hints..:) |
||||||||||||||
2016-05-27 19:46:40
I have the right to vote finally vuhuuuuu! |