| 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
|
||||||||||||||
|
2024-04-18 01:37:25
hint : a node cannot have 2 parents |
||||||||||||||
|
2024-02-11 17:06:51
should have added a test case with disconnected components |
||||||||||||||
|
2023-08-19 06:23:21
bad problem. Maybe there's duplicate edge in problem like: {1, 2} {2, 1} E==N-1 property maybe not happening but still a Tree Last edit: 2023-08-19 06:24:06 |
||||||||||||||
|
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! |
||||||||||||||
|
2021-11-29 09:25:50
AC in one go.... Just check cycle and connected components. |
||||||||||||||
|
2021-08-17 21:50:21
Number of connected component 1 And M < N ... Enough to get AC; |
||||||||||||||
|
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 :) |
||||||||||||||
|
2021-06-30 15:19:14
easy one |
||||||||||||||
|
2021-05-29 00:17:25
Some test cases that will help you: 9 8 7 8 2 3 8 3 6 3 5 3 7 9 9 1 9 4 YES 9 8 1 2 2 3 3 4 1 4 5 6 7 8 9 7 8 9 NO |
||||||||||||||
|
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 |
||||||||||||||
RSS