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

pranjulpal18: 2020-03-14 07:57:25

A simple DSU problem.

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


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