Path Graph?

题目描述

You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1, 2, \dots, N$ , and the edges are numbered $1, 2, \dots, M$ .
Edge $i \, (i = 1, 2, \dots, M)$ connects vertices $u_i$ and $v_i$ . Determine if this graph is a path graph.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.

What is a path graph?

A graph with $N$ vertices numbered $1, 2, \dots, N$ is said to be a path graph if and only if there is a sequence $(v_1, v_2, \dots, v_N)$ that is a permutation of $(1, 2, \dots, N)$ and satisfies the following conditions:

For all $i = 1, 2, \dots, N-1$ , there is an edge connecting vertices $v_i$ and $v_{i+1}$ . If integers $i$ and $j$ satisfies $1 \leq i, j \leq N$ and $|i - j| \geq 2$ , then there is no edge that connects vertices $v_i$ and $v_j$ .

输入格式

The input is given from Standard Input in the following format: $N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

Print $Yes$ if the given graph is a path graph; print $No$ otherwise.

Yes

2 0

No

No

提示

$2 \leq N \leq 2 \times 10^5$ $0 \leq M \leq 2 \times 10^5$ $1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)$ All values in the input are integers. The graph given in the input is simple.Illustrated below is the given graph, which is a path graph. example_00
Illustrated below is the given graph, which is not a path graph. example_01
Illustrated below is the given graph, which is not a path graph. example_02

标签: AtCoder|abc287C

来源

AtCoder|abc287C

#4528. Path Graph?

Path Graph?

Path Graph?

题目描述

输入格式

输出格式

提示

来源

还没有账户？

登录