102882: [AtCoder]ABC288 C - Don’t be cycle
Description
Score : $300$ points
Problem Statement
You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.
What is a simple undirected graph?
A simple undirected graph is a graph without self-loops or multi-edges whose edges have no direction.
What is a cycle?
A cycle in a simple undirected graph is a sequence of vertices $(v_0, v_1, \ldots, v_{n-1})$ of length at least $3$ satisfying $v_i \neq v_j$ if $i \neq j$ such that for each $0 \leq i < n$, there is an edge between $v_i$ and $v_{i+1 \bmod n}$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq A_i, B_i \leq N$
- The given graph is simple.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$
Output
Print the answer.
Sample Input 1
6 7 1 2 1 3 2 3 4 2 6 5 4 6 4 5
Sample Output 1
2
One way to remove cycles from the graph is to delete the two edges between vertex $1$ and vertex $2$ and between vertex $4$ and vertex $5$.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print $2$.
Sample Input 2
4 2 1 2 3 4
Sample Output 2
0
Sample Input 3
5 3 1 2 1 3 2 3
Sample Output 3
1
Input
题意翻译
给定一个简单无向图，要求删除最小的边数（可以不删）使得图中没有环。Output
问题描述
给你一个包含 N 个顶点和 M 条边的简单无向图。顶点编号为 1 到 N，第 i 条边连接顶点 A_i 和顶点 B_i。 让我们删除零条或多条边以移除图中的循环。求出为了达到这个目的，必须删除的边的最小数量。
什么是简单无向图？
简单无向图是一个没有自环或多边的图，其边没有方向。
什么是循环？
在一个简单无向图中，一个 循环 是一个长度至少为 3 的顶点序列 $(v_0, v_1, \ldots, v_{n-1})$，满足 $v_i \neq v_j$ 如果 $i \neq j$，并且对于每个 $0 \leq i < n$，顶点 $v_i$ 和顶点 $v_{i+1 \bmod n}$ 之间存在一条边。
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq A_i, B_i \leq N$
- 给定的图是简单的。
- 输入中的所有值都是整数。
输入
输入通过标准输入给出以下格式：
$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$
输出
打印答案。
样例输入 1
6 7 1 2 1 3 2 3 4 2 6 5 4 6 4 5
样例输出 1
2
一种移除图中循环的方法是删除顶点 1 和顶点 2 之间的两条边以及顶点 4 和顶点 5 之间的两条边。 没有一种方法可以通过删除一条或更少的边来移除图中的循环，所以你应该打印 2。
样例输入 2
4 2 1 2 3 4
样例输出 2
0
样例输入 3
5 3 1 2 1 3 2 3
样例输出 3
1