PT07Y - Is it a tree


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

hide comments
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

nayeem_joy: 2019-08-10 15:17:34

two cases should be handled here , if u feel struggle
then make this url as search
"https://github.com/joy-mollick/Problem-Solving-Solutions/blob/master/SPOJ-PT07Y%20-%20Is%20it%20a%20tree.cpp"


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