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-05-19 19:24:16 Mihir Saxena
Getting sigsegv error, what can be the possibility? Tried another approach, didn't create an array, instead used the union find algorithm directly on the edges and then in the end, checked the condition of connected graph, still got a WA Last edit: 2016-05-19 20:02:58 |
||||||||||||||
2016-05-13 22:20:50 Luis Herrera
Interesting problem. Hints: A graph is a tree if: - It has no cycles - It is connected |
||||||||||||||
2016-05-12 20:38:21
if any node is not connected to rest of nodes then it should YES or NO |
||||||||||||||
2016-05-01 10:23:14 dinkar
Nice problem, got to learn about union find. |
||||||||||||||
2016-04-15 03:22:32
Did you guys build the graph in order to do DFS? |
||||||||||||||
2016-03-12 12:31:25 sharif ullah
just use union find check if there is a loop! |
||||||||||||||
2016-03-06 17:12:11 vimal
accepted on codechef... WA here... :D UPDATE : solved. hint:what are 3 important prop. of a tree ? Last edit: 2016-03-06 17:24:21 |
||||||||||||||
2016-02-16 16:56:15 Neeraj Singh Aithani
Actually Test Cases are very weak my solution for 4 3 4 2 4 3 2 1 is NO.But it is AC |
||||||||||||||
2016-01-22 21:14:52
i am using matrix to represent it's structure as a graph but getting sigsev error |
||||||||||||||
2016-01-16 06:00:11 Aqib Ahmed J
Tree doesn't have loops ! Cost me one WA :| |