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-06-22 13:47:25
AC in 2nd go... read the method of finding connected components. Good question |
||||||||||||||
2015-06-14 19:41:40 Sukeesh
input : 7 6 3 1 3 2 2 4 2 5 1 6 1 7 What would be the answer for this? |
||||||||||||||
2015-06-11 21:59:22 Linus
Very good question ..learned a lot ...read this .... https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf .....The way here union find is described is just awesome .... my 25 !!!!! |
||||||||||||||
2015-06-11 20:12:42 peeyush taneja
NIce question |
||||||||||||||
2015-06-08 23:30:52 mayank
They are not checking for edge disconnectivity in graph (ie. already given m=n-1).Good problem though. |
||||||||||||||
2015-06-05 10:18:35 Manish Sombansh
I am trying to solve this problem using union-find. but am getting TLE. Can anybody please tell me what's the error? My source code : http://ideone.com/EogUfW |
||||||||||||||
2015-06-04 16:26:13 BRAIN
using dfs or bfs to check connect and using FindSet and Union of Kruskal algorithm to check circle |
||||||||||||||
2015-05-29 17:52:14 Shubham Khilari
my first problem in graphs. solved in O(n^2).Did not use any stl or dfs bfs.Just try to find if there is a cycle or not..and then u r done.Executes in 0.09.Is there a faster way? PS: I got two WAs for using just int...so use long long int(that was my bad lol ) |
||||||||||||||
2015-05-26 10:42:53 Aman Agarwal
1st question of graph.. :) |
||||||||||||||
2015-05-24 18:01:15
Just one graph traversal, no need to apply union find!!!! |