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
prithvi_3d2y: 2020-02-06 16:14:54

SImple AC:
Check if connected components = 1 & nodes - 1 = edges.

sangmai: 2020-01-16 11:57:27

dfs with recursion gets TLE, use queue instead

i_master: 2019-12-30 23:00:07

Just think about it conceptually. What is a tree? A tree is a connected undirected acyclic graph.

Connected -> all vertices must be connected to at least one other vertex
Undirected -> an edge points in both directions (u,v) and (v,u)
Acyclic -> (a <-> b <-> c)
Not Acyclic (a <-> b <-> c <-> a) = Bad

karandeep09: 2019-12-30 16:38:25

if n==no. of times dfs runs && n==m+1

r15habhgup11: 2019-11-05 11:46:00

Can someone plzz tell me answer of this case and why
6 5
1 4
2 4
3 4
5 4
5 6

invincibel: 2019-09-23 08:40:58

use union-find much better for this problem

mriow: 2019-08-21 07:55:05


Any connected graph G with n vertices and (n-1) edges is a tree (No need to search for cycles, only connection)

Last edit: 2019-08-21 07:56:17
ashishgh1997: 2019-08-17 08:05:37

The tree may not be a binary tree. A node may have more than 3 childs

veerendrasd_9: 2019-07-20 19:35:16

AC only if one considers it as directed Graph.

Last edit: 2019-07-20 19:36:10
an09mous: 2019-07-03 13:47:50

For a graph to be a tree, there must be no cycles and not any isolated vertices. So number of edges will always be n-1. If edges are exactly equal to n-1, then we just have to check if there is a cycle or not.

Last edit: 2019-07-03 13:48:05

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