102872: [AtCoder]ABC287 C - Path Graph?
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:
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.
Sample Input 2
2 0
Sample Output 2
No
Illustrated below is the given graph, which is not a path graph.
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.
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），满足以下条件：
约束条件
- 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
下图所示为给定的路径图。
样例输入2
2 0
样例输出2
No
下图所示为给定的非路径图。
样例输入3
5 5 1 2 2 3 3 4 4 5 5 1
样例输出3
No
下图所示为给定的非路径图。