102923: [Atcoder]ABC292 D - Unicyclic Components
Description
Score : $400$ points
Problem Statement
You are given an undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.
Determine whether every connected component in this graph satisfies the following condition.
- The connected component has the same number of vertices and edges.
Notes
An undirected graph is a graph with edges without direction.
A subgraph of a graph is a graph formed from a subset of vertices and edges of that graph.
A graph is connected when one can travel between every pair of vertices in the graph via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq u_i \leq v_i \leq N$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $u_1$ $v_1$ $\vdots$ $u_M$ $v_M$
Output
If every connected component satisfies the condition, print Yes; otherwise, print No.
Sample Input 1
3 3 2 3 1 1 2 3
Sample Output 1
Yes
The graph has a connected component formed from just vertex $1$, and another formed from vertices $2$ and $3$.
The former has one edge (edge $2$), and the latter has two edges (edges $1$ and $3$), satisfying the condition.
Sample Input 2
5 5 1 2 2 3 3 4 3 5 1 5
Sample Output 2
Yes
Sample Input 3
13 16 7 9 7 11 3 8 1 13 11 11 6 11 8 13 2 11 3 3 8 12 9 11 1 11 5 13 3 12 6 9 1 10
Sample Output 3
No
Input
题意翻译
- 有 $n$ 个顶点。 - 有 $m$ 条无向边。 - 第 $i$ 条无向边连接 $u_i,v_i$。 - 若 $(u_i,v_i)$ 和 $(u_j,v_j)$ 是同一条边，当且仅当 $i=j$。 - 问是否所有连通块里的点数和边数都相等。 - $1\le n,m\le 2\times 10^5$，$1\le u_i\le v_i\le n$。Output
问题描述
给你一个无向图，包含 N 个编号为 1 到 N 的顶点和 M 个编号为 1 到 M 的边。第 i 条边连接顶点 ui 和顶点 vi。
确定这个图中的每个连通分量是否满足以下条件。
- 连通分量具有相同数量的顶点和边。
注意
一个 无向图 是没有方向的边的图。
一个图的 子图 是由该图的顶点和边的子集形成的图。
一个图是 连通的 当且仅当可以沿着图中的边在图中的每对顶点之间移动。
一个 连通分量 是一个连通子图，不属于任何更大的连通子图。
约束
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq u_i \leq v_i \leq N$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $M$ $u_1$ $v_1$ $\vdots$ $u_M$ $v_M$
输出
如果每个连通分量都满足条件，则输出 Yes；否则，输出 No。
样例输入 1
3 3 2 3 1 1 2 3
样例输出 1
Yes
图中有一个仅包含顶点 1 的连通分量，另一个包含顶点 2 和 3 的连通分量。
前者有一条边（边 2），后者有两条边（边 1 和 3），满足条件。
样例输入 2
5 5 1 2 2 3 3 4 3 5 1 5
样例输出 2
Yes
样例输入 3
13 16 7 9 7 11 3 8 1 13 11 11 6 11 8 13 2 11 3 3 8 12 9 11 1 11 5 13 3 12 6 9 1 10
样例输出 3
No