#C248. Check if a Graph is a Tree
Check if a Graph is a Tree
Check if a Graph is a Tree
You are given an undirected graph with n vertices (numbered from 0 to n-1) and m edges. Your task is to determine whether the graph forms a tree.
A graph is a tree if and only if:
- It has exactly n-1 edges.
- It is connected, i.e. there is a path between any two vertices.
Recall that the mathematical condition for being a tree is:
$$ m=n-1 \quad \text{and} \quad \forall v \in \{0, 1, \dots, n-1\}, \text{ vertex } v \text{ is reachable from vertex } 0.$$
You should read the input from standard input and output the result to standard output. If the graph is a tree, print YES
; otherwise, print NO
.
inputFormat
The first line contains two integers n
and m
— the number of vertices and the number of edges, respectively.
The following m
lines each contain two integers u
and v
indicating that there is an undirected edge connecting vertex u
and vertex v
.
It is guaranteed that 0 ≤ u, v < n
.
outputFormat
Output a single line containing YES
if the given graph is a tree, otherwise output NO
.
5 4
0 1
0 2
0 3
1 4
YES