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
harry_shit: 2020-08-18 13:53:43

simple dfs will do the the work

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
no of connected compo ==1 && m=n-1

picchi_67: 2020-06-13 09:10:43

easy DSU problem...but you have to know what is tree...
1.must have all the nodes connected. cycle
3.edges are undirected.
4.must have one edge.

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 ->
if the connected components is equals to one after depth first search
if the number of edges == number of nodes-1

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

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