AT_abc288_c.[ABC288C] Don’t be cycle

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 $N$ 个顶点、 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$ ，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$ 。你可以从图中删除 $0$ 条或多条边，使得图中不包含任何环。请你求出需要删除的最少边数。

简单无向图是指不包含自环和重边，且边没有方向的图。

环的定义：一个简单无向图包含环，指存在长度不小于 $3$ 的顶点序列 $(v_0, v_1, \ldots, v_{n-1})$ ，满足 $i \neq j$ 时 $v_i \neq v_j$ ，并且对于每个 $0 \leq i < n$ ， $v_i$ 和 $v_{(i+1) \bmod 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
```
输入#2
```
4 2
1 2
3 4
```
输出#2
```
0
```
输入#3
```
5 3
1 2
1 3
2 3
```
输出#3
```
1
```

说明/提示

限制条件

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq N$
给定的图是简单图
所有输入均为整数

样例解释 1

例如，可以删除连接顶点 $1$ 和顶点 $2$ 的边，以及连接顶点 $4$ 和顶点 $5$ 的边这两条边，使得图中不再包含环。无法通过删除 $1$ 条或更少的边使图中不包含环，因此输出 $2$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页