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
|
r0bo_dart:
2015-06-22 13:47:25
AC in 2nd go... read the method of finding connected components. Good question |
|
Sukeesh:
2015-06-14 19:41:40
input :
|
|
Linus:
2015-06-11 21:59:22
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 !!!!!
|
|
peeyush taneja:
2015-06-11 20:12:42
NIce question |
|
mayank:
2015-06-08 23:30:52
They are not checking for edge disconnectivity in graph (ie. already given m=n-1).Good problem though.
|
|
Manish Sombansh:
2015-06-05 10:18:35
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 |
|
BRAIN:
2015-06-04 16:26:13
using dfs or bfs to check connect and using FindSet and Union of Kruskal algorithm to check circle |
|
Shubham Khilari:
2015-05-29 17:52:14
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?
|
|
Aman Agarwal:
2015-05-26 10:42:53
1st question of graph.. :)
|
|
anksin:
2015-05-24 18:01:15
Just one graph traversal, no need to apply union find!!!! |
| 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