102872: [AtCoder]ABC287 C - Path Graph?

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：2 Solved：0

Description

Score : $300$ points

Problem Statement

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

Constraints

  • $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.

Input

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$

Output

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

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

example_00

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

example_01

Sample Input 3

5 5
1 2
2 3
3 4
4 5
5 1

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

example_02

Input

题意翻译

给定一个图，判断这个图是否为一条链。

Output

得分：300分

问题描述

给你一个具有N个顶点和M条边的简单无向图。顶点编号为1, 2, ..., N，边编号为1, 2, ..., M。
第i条边（i = 1, 2, ..., M）连接顶点u_i和v_i。

判断这个图是否为路径图。

什么是简单无向图？ 一个简单无向图是一个没有自环或多边形的图，其边没有方向。

什么是路径图？ 一个具有N个顶点编号为1, 2, ..., N的图被称为路径图，当且仅当存在一个排列（v_1, v_2, ..., v_N），满足以下条件：
  • 对于所有i = 1, 2, ..., N-1，存在一条连接顶点v_i和v_{i+1}的边。
  • 如果整数i和j满足1 \leq i, j \leq N并且|i - j| \geq 2，则不存在连接顶点v_i和v_j的边。

约束条件

  • 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, ..., M)
  • 输入中的所有值都是整数。
  • 输入给定的图是简单的。

输入

输入从标准输入以以下格式给出：

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出

如果给定的图是路径图，则打印Yes；否则打印No。

样例输入1

4 3
1 3
4 2
3 2

样例输出1

Yes

下图所示为给定的路径图。

example_00

样例输入2

2 0

样例输出2

No

下图所示为给定的非路径图。

example_01

样例输入3

5 5
1 2
2 3
3 4
4 5
5 1

样例输出3

No

下图所示为给定的非路径图。

example_02

Source/Category

加入题单

算法标签：