SPOJ.com - Problem PT07Y

PT07Y - Is it a tree

#dfs

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	sa03195100: 2020-02-18 11:58:55 2 5 7 0 0 0 0 0 0 0 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 5 15 0 0 0 0 2 0 2 0 0 0 0 1 2 0 1 0 0 0 1 0 2 0 2 2 0 1 2 0 0 0 2 1 0 2 0 1 0 2 0 0 0 0 0 0 0 0 0 0 1 0 2 0 0 1 2 0 0 2 0 0 0 2 1 0 2 0 0 0 0 0 3 0 0 0 0 Last edit: 2020-02-18 12:00:01
	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 AC if n==no. of times dfs runs && n==m+1 YES
	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 HINT: 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

Submit solution!

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