| 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
|
||||||||||||||
|
2020-08-14 16:34:59
AC in one go!! Thanks to comment on connected component |
||||||||||||||
|
2020-06-22 19:19:21
simple one using no of connected compo ==1 && m=n-1 |
||||||||||||||
|
2020-06-13 09:10:43
easy DSU problem...but you have to know what is tree... 1.must have all the nodes connected. 2.no cycle 3.edges are undirected. 4.must have one edge. |
||||||||||||||
|
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 |
||||||||||||||
|
2020-04-25 20:05:26
The main thing to remember to check weather tree -> if the connected components is equals to one after depth first search if the number of edges == number of nodes-1 |
||||||||||||||
|
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. |
||||||||||||||
|
2020-04-20 08:43:14
@sangmai, no it doesn't give TLE for recursive DFS. |
||||||||||||||
|
2020-04-15 09:43:55
Check if no_of_connected_components==1 && no_of_edges==N-1; |
||||||||||||||
|
2020-03-19 11:17:03
learnt depth first search using adjacent list |
||||||||||||||
|
2020-03-14 07:57:25
A simple DSU problem. |
||||||||||||||
RSS