| 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
|
||||||||||||||
|
2016-01-12 05:10:29 RADHE SHYAM LODHI
AC union set 0.00 .. |
||||||||||||||
|
2016-01-06 06:33:31
Got AC. Just run the single DFS: 1) Check for loops - grey (visited, but not left) vertex found - loop, output "NO" 2) Check for single connected component - after DFS all vertices should be colored black (visited and left) |
||||||||||||||
|
2015-12-30 12:34:06 Deepak
thanks @rahul for your hint |
||||||||||||||
|
2015-12-25 10:01:02 AASHISH KUMAR
AC in one go :) yeyii |
||||||||||||||
|
2015-12-23 19:29:15 rahul
i think this question can be solved easily if you focus on checking how many connected component it has if it has one connected component and edges=nodes-1 it will b accepted |
||||||||||||||
|
2015-12-23 15:22:25 ankurverma1994
Got AC with Union Find in 1st Attempt in Java. Don't know why its showing WA when using DFS in Java and getting AC(using same DFS code as in Java) in C++ with same logic... :( |
||||||||||||||
|
2015-12-08 09:41:20 MAYANK NARULA
Well This problem gave me some WAs .!!!!.... Maybe Graph has Self - loops at some vertices.. |
||||||||||||||
|
2015-12-04 22:14:22
Yeaahh !! Finally got an AC After 3 WA. People who are new to graph (as I was) should try to look how to implement a graph and then check the ewquired conditions for a graph to be a tree. There are 3 conditions, If you want to learn try to check all 3 and not the only easiest one. Geeksforgeeks has a similar question, you can view it to understand the working of graphs. |
||||||||||||||
|
2015-11-21 14:23:58
For people Union set gets you done in 0.0 s checking conditions are for tree are The inputs are integer's from 1 to n 1. input must be in order => in the m line 2 3 is allowed but 3 2 in input is not allowed (i got this doubt so i wasted an hour thinking about this or else it was a matter of 5 mins . ) NO 2. if a b are having edge . b should not be connected to any NO 3. if it is not connected , check for repetition of b in parents of a 's .if b is there ,it is cycle NO , else join them 4. at the end ,loop and find if there are any elements with no , count them . if it is not 1 then NO 5. at the end the answer is YES if all the 4 fail Have fun very easy one ac in one go :) Last edit: 2015-11-21 14:34:41 |
||||||||||||||
|
2015-11-13 21:27:43
I think if you aren't confortable with graphs, you should search for a solution and understand it by using the hand-execution on a paper... |
||||||||||||||
RSS