← 返回题目
题库练习 二分图化
← 上一题 下一题 →

A5438 | 二分图化

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的**简单无向图**。
图中包含顶点 $1, 2, \ldots, N$，第 $i$ 条边 $(1 \le i \le M)$ 连接顶点 $u_i$ 和 $v_i$。

你可以进行以下操作若干次（可以为 0 次）：

- 选择一条尚未被删除的边，将其删除。

你的目标是让图变成**二分图**。
请输出最少需要进行多少次操作，才能使删除操作后的图成为二分图。

---

### 什么是“简单图”？

若一个图**没有自环**（即不存在 $u_i = v_i$）且**没有重边**（不存在 $u_i = u_j$ 且 $v_i = v_j$ 的不同边对），则称该图为**简单图**。

---

### 什么是“二分图”？

如果能够将图中每个顶点染成黑色或白色，使得：

- 对于每一条边，连接的两个顶点颜色不同，

则称该图为**二分图**。

输入格式

从标准输入读取：

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

输出格式

输出一个整数，表示最少需要删除多少条边，才能使图成为二分图。

输入输出样例

输入 #1
5 8
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5
输出 #1
2
输入 #2
2 1
1 2
输出 #2
0
输入 #3
10 20
5 9
1 4
3 8
1 6
4 10
5 7
5 6
3 7
3 6
5 10
1 3
3 4
6 7
1 2
4 7
1 5
1 9
9 10
4 5
8 9
输出 #3
5
C++ 编辑器
输入
输出