题目求助,悬关
  • 板块灌水区
  • 楼主AKIOI_114514
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/2/23 10:12
  • 上次更新2024/2/23 12:33:04
查看原帖
题目求助,悬关
1284230
AKIOI_114514楼主2024/2/23 10:12

小明在学校的编程课上了解到了关于二分图的相关知识,所谓的二分图是一种特殊的图,图中的所有顶点可以分为两个不相交的集合,而图中的所有边的两个顶点都分属于这两个集合。

换句话来说,二分图是可以进行黑白染色的图,即给图中所有顶点都涂上黑色或者白色,使得每条边的两个端点都异色。

现在小明想知道,对于任意的一个n个顶点m条边的无向图,通过删去一条边使其变为二分图的方案数是多少?

输入输出格式

输入格式:

第一行输入两个数n、m,表示图的顶点数和边数 接下来m行,每行两个数x、y,表示一条边(编号1~m)

输出格式:

第一行输出一个数k,表示答案方案数 第二行输出k个数,表示k条边的编号,升序排列 输入输出样例 输入样例:

4 4 1 2 1 3 2 4 3 4

输出样例:

4 1 2 3 4

样例说明:

有4种删除方案,删除{1, 2, 3, 4}号边中的任意一个都可以使图变为二分图。

测试点 一共10个测试点,每个测试点10分

每个测试点时间限制为1s,空间限制为128MB

测试点:

测试点1~10:1≤n≤105,1≤m≤1061 \le n \le 10^5,1 \le m \le 10^6

2024/2/23 10:12
加载中...