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
|
le_louch007:
2024-04-18 01:37:25
hint : a node cannot have 2 parents |
|
mushfiq123:
2024-02-11 17:06:51
should have added a test case with disconnected components
|
|
k124k3n:
2023-08-19 06:23:21
bad problem. Maybe there's duplicate edge in problem like:
|
|
zeyf:
2022-04-11 00:51:23
You can just use a UnionFind/DisjointSet for all other cases and whenever there is a failed union (returns false), this is the case where both nodes u and v are part of the same set already. This means it is not a tree in it's current form! |
|
amansingh_20:
2021-11-29 09:25:50
AC in one go....
|
|
shofiqur_052:
2021-08-17 21:50:21
Number of connected component 1
|
|
avx_5801:
2021-07-09 11:08:30
You have to also check self loop condition,then you get AC in one GO by Using simple dfs :) |
|
mortal_beast:
2021-06-30 15:19:14
easy one |
|
the_art_maniac:
2021-05-29 00:17:25
Some test cases that will help you:
|
|
yasser1110:
2021-02-19 14:54:05
+1 @jrseinc disjoint union set solution is the most straightforward one. Even though adjacency matrix and adjacency list solutions also work. Last edit: 2021-02-19 14:54:25 |
| 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