← 返回题单
题单练习 枚举
← 上一题 下一题 →

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++ 编辑器
输入
输出