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
|
saurabh_shinde:
2020-08-14 16:34:59
AC in one go!! Thanks to comment on connected component |
|
adikrmishra_1:
2020-06-22 19:19:21
simple one using
|
|
picchi_67:
2020-06-13 09:10:43
easy DSU problem...but you have to know what is tree...
|
|
afaiyaz:
2020-06-11 12:44:01
If anyone getting TLE using recursive dfs just pass the vector to dfs function as a const reference.(in c++ ofcourse) Last edit: 2020-06-11 12:44:44 |
|
soumen_1696:
2020-04-25 20:05:26
The main thing to remember to check weather tree ->
|
|
yourmom__:
2020-04-21 07:30:05
I heard people say that in java, Scanner is causing TLE. It's not true, as mine got accepted using Scanner. I used BFS. |
|
samio:
2020-04-20 08:43:14
@sangmai, no it doesn't give TLE for recursive DFS. |
|
zoso_floyd:
2020-04-15 09:43:55
Check if no_of_connected_components==1 && no_of_edges==N-1; |
|
abhigurjeet:
2020-03-19 11:17:03
learnt depth first search using adjacent list
|
|
pranjulpal18:
2020-03-14 07:57:25
A simple DSU problem. |
| 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