| 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
|
||||||||||||||
|
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 |
||||||||||||||
|
2019-06-22 15:19:05
check for cycle and if not found then check all nodes are visited . |
||||||||||||||
|
2019-06-06 20:10:39
@itsshubham_m12 clearly its given in question that its undirected graph |
||||||||||||||
|
2019-05-29 11:33:31
use dfs....ac in one go |
||||||||||||||
|
2019-04-24 10:37:57
To check if connected better use optimized DSU than DFS. |
||||||||||||||
|
2019-04-22 17:12:34
Is the graph directed or not?? |
||||||||||||||
|
2019-03-15 00:05:27
If you're using Java and has the TLE, please never use Scanner instead of BufferReader |
||||||||||||||
|
2019-03-13 10:10:24
Tree is undirected! Only check for 2 cases :- 1) e=n-1 2) Only 1 conected component! |
||||||||||||||
|
2019-03-06 10:24:51
Very good introduction to DFS. 2 points to keep in mind: * a tree has no cycles * a tree has no isolated node |
||||||||||||||
|
2019-03-05 02:51:04
test cases 've been fixed to be undirected Last edit: 2019-03-05 02:51:18 |
||||||||||||||
RSS