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
|
an09mous:
2019-07-03 13:47:50
For a graph to be a tree, there must be no cycles and not any isolated vertices. So number of edges will always be n-1. If edges are exactly equal to n-1, then we just have to check if there is a cycle or not. Last edit: 2019-07-03 13:48:05 |
|
gyanendra371:
2019-06-22 15:19:05
check for cycle and if not found then check all nodes are visited . |
|
itsmysyntax:
2019-06-06 20:10:39
@itsshubham_m12 clearly its given in question that its undirected graph |
|
nishit5:
2019-05-29 11:33:31
use dfs....ac in one go
|
|
klmo:
2019-04-24 10:37:57
To check if connected better use optimized DSU than DFS. |
|
itsshubham_m12:
2019-04-22 17:12:34
Is the graph directed or not??
|
|
ll14:
2019-03-15 00:05:27
If you're using Java and has the TLE, please never use Scanner instead of BufferReader |
|
mynk322:
2019-03-13 10:10:24
Tree is undirected!
|
|
haiderbaig:
2019-03-06 10:24:51
Very good introduction to DFS.
|
|
knir0103:
2019-03-05 02:51:04
test cases 've been fixed to be undirected Last edit: 2019-03-05 02:51:18 |
| 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