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
Anurag Pasi: 2015-06-30 13:39:28

Implementation of DFS by Adjacency list+STL 0.00 sec and 3.4Mb :)
There are total 3 conditions to check for a tree :
1) connected graph
2) non-cyclic or acyclic
3) n-1==m
but actually u hav to check only 2 conditions if u think :)

Last edit: 2015-06-30 13:41:24
gamer496: 2015-06-29 19:36:41

@Sukeesh YES

r0bo_dart: 2015-06-22 13:47:25

AC in 2nd go... read the method of finding connected components. Good question

Sukeesh: 2015-06-14 19:41:40

input :
7 6
3 1
3 2
2 4
2 5
1 6
1 7

What would be the answer for this?

Linus: 2015-06-11 21:59:22

Very good question ..learned a lot this .... .....The way here union find is described is just awesome .... my 25 !!!!!

peeyush taneja: 2015-06-11 20:12:42

NIce question

mayank: 2015-06-08 23:30:52

They are not checking for edge disconnectivity in graph (ie. already given m=n-1).Good problem though.

Manish Sombansh: 2015-06-05 10:18:35

I am trying to solve this problem using union-find. but am getting TLE. Can anybody please tell me what's the error? My source code :

BRAIN: 2015-06-04 16:26:13

using dfs or bfs to check connect and using FindSet and Union of Kruskal algorithm to check circle

Shubham Khilari: 2015-05-29 17:52:14

my first problem in graphs. solved in O(n^2).Did not use any stl or dfs bfs.Just try to find if there is a cycle or not..and then u r done.Executes in 0.09.Is there a faster way?

I got two WAs for using just use long long int(that was my bad lol )

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