题意：
删掉若干条边使原图成为二分图的方案数。
题解：
考虑DFS树。
答案为所有奇环的交减掉偶环的并。
这里的环指的是由一条非树边和若干条树边组成的环。
如果一个奇环和偶环在树边上有交集，那么删掉交集部分后会形成新的奇环，而删掉奇环的非树边则会破坏奇环。
首先考虑只有一个奇环的情况。
首先奇环的非树边显然是可以删掉的，删掉后破坏了奇环。
其次，奇环的树边，只要不被另一个偶环覆盖，那么也可以删（如果被覆盖了，删掉后会拼成一个新的奇环）
考虑由多个奇环的情况。
答案是所有奇环的公共部分。
直接在树上打标记即可。
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 10000;
struct State
{
int_t depth;
int_t vertex;
bool operator<(const State &x) const
{
return depth < x.depth;
}
State(int_t vertex = -1, int_t depth = 0)
{
this->depth = depth;
this->vertex = vertex;
}
} seq[20][LARGE * 3 + 1];
struct Edge
{
int_t to;
int_t id;
int_t from = -1;
};
int_t count = 0;
int_t first[LARGE + 1];
int_t depth[LARGE + 1];
std::vector<Edge> graph[LARGE + 1];
std::vector<Edge> nonetree[LARGE + 1];
std::vector<int_t> stage[LARGE + 1];
Edge inEdge[LARGE + 1];
bool visited[LARGE + 1];
int_t mark[LARGE + 1];
int_t parent[LARGE + 1];
int_t n, m;
void DFS0(int_t vertex, int_t from = -1, int_t depth = 1)
{
if (visited[vertex])
return;
// cout << "visiting " << vertex << endl;
::parent[vertex] = from;
stage[depth].push_back(vertex);
::depth[vertex] = depth;
visited[vertex] = true;
seq[0][++count] = State(vertex, depth);
if (first[vertex] == 0)
first[vertex] = count;
for (auto &edge : graph[vertex])
{
if (visited[edge.to] && edge.to != from && ::depth[edge.to] > ::depth[vertex])
{
nonetree[vertex].push_back(edge);
}
else if (visited[edge.to] == false)
{
inEdge[edge.to] = edge;
DFS0(edge.to, vertex, depth + 1);
seq[0][++count] = State(vertex, depth);
if (first[vertex] == 0)
first[vertex] = count;
}
}
}
void init()
{
for (int_t i = 1; (1 << i) <= count; i++)
{
for (int_t j = 1; j + (1 << i) - 1 <= count; j++)
{
seq[i][j] = std::min(seq[i - 1][j], seq[i - 1][j + (1 << (i - 1))]);
}
}
}
int_t getLCA(int_t v1, int_t v2)
{
v1 = first[v1];
v2 = first[v2];
if (v1 > v2)
std::swap(v1, v2);
int_t i = std::log2(v2 - v1 + 1);
return std::min(seq[i][v1], seq[i][v2 - (1 << i) + 1]).vertex;
}
int main()
{
cin >> n >> m;
for (int_t i = 1; i <= m; i++)
{
int_t from, to;
cin >> from >> to;
graph[from].push_back(Edge{to, i});
graph[to].push_back(Edge{from, i});
}
for (int_t i = 1; i <= n; i++)
{
if (visited[i] == false)
{
DFS0(i);
}
}
init();
int_t count = 0;
std::vector<Edge> evens;
for (int_t i = 1; i <= n; i++)
{
for (auto &edge : nonetree[i])
{
int_t dis = depth[i] + depth[edge.to] - 2 * depth[getLCA(edge.to, i)] + 1;
int_t mark;
//偶环
if (dis % 2 == 0)
{
mark = -1;
}
else
{ //奇环
mark = 1;
count++;
evens.push_back(Edge{i, edge.id, edge.to});
}
::mark[i] += mark;
::mark[edge.to] += mark;
::mark[getLCA(edge.to, i)] -= 2 * mark;
}
}
for (int_t i = n; i >= 2; i--)
{
for (int_t vtx : stage[i])
{
mark[parent[vtx]] += mark[vtx];
}
}
std::vector<int_t> result;
if (count == 0)
{
for (int_t i = 1; i <= m; i++)
{
result.push_back(i);
}
}
else if (count == 1)
{
int_t v1 = evens[0].from;
int_t v2 = evens[0].to;
int_t lca = getLCA(v1, v2);
result.push_back(evens[0].id);
while (v1 != lca)
{
if (mark[v1] == 1)
{
result.push_back(inEdge[v1].id);
}
v1 = parent[v1];
}
while (v2 != lca)
{
if (mark[v2] == 1)
{
result.push_back(inEdge[v2].id);
}
v2 = parent[v2];
}
}
else if (count > 1)
{
for (int_t i = 1; i <= n; i++)
{
if (parent[i] != -1 && mark[i] == evens.size())
{
result.push_back(inEdge[i].id);
}
}
}
std::sort(result.begin(), result.end());
cout << result.size() << endl;
for (int_t x : result)
cout << x << " ";
cout << endl;
return 0;
}