PT07Y - Is it a tree

You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.


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).


Print YES if the given graph is a tree, otherwise print NO.


3 2
1 2
2 3


hide comments
karthik1997: 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
garmel: 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...

archit saxena: 2015-11-11 09:42:47

can the name of nodes be fractions

dk619: 2015-11-02 23:21:16

Disjoint set data structures is the best

Last edit: 2015-11-03 14:17:06
dragonemperor: 2015-10-21 12:07:39

Union find got AC. At first I set parent of each node as -1. This got TLE. Setting parent[a]=a worked like a charm

Vaibhav Malik: 2015-10-06 20:54:26

AC in one GO :)

jarvis: 2015-09-28 23:37:35

First graph :) first DFS :) love it <3 after 5 WA

Sarthak Munshi: 2015-09-25 14:29:21

Check :
1) edges=nodes-1
2) graph is connected(kosaraju or simple dfs will do )

[Mayank Pratap]: 2015-09-22 14:16:28

Enjoyed this problem... :)

jyotman94: 2015-09-19 21:03:46

First Graph Problem :) AC

Added by:Thanh-Vy Hua
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Co-author Amber