给定 $n$ 个点，$m$ 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。
第一行包含两个正整数 $n, m$ ($n, m \leq 10^6$)，分别表示点数和边数。
第 $2 \sim m+1$ 行，每行两个正整数 $x, y$ ($1 \leq x, y \leq n; x \neq y$)，表示有一条 $(x, y)$ 的边。
第一行输出一个整数，表示能删除的边的个数。
第二行按照从小到大的顺序输出能删除的边的序号。
引理：一个无向图 $G$ 为二分图的充分必要条件为 $G$ 中没有奇数长度的圈。
证明略。
因此，我们只需去找一些边，使得将它删去后原图没有奇圈。
首先，若原图本身没有奇圈，则删除所有边后均满足题意 (没有奇圈)，因此直接输出所有边即可。
否则 (原图有奇圈)，我们建出原图的一棵 dfs 树。那么每一个奇圈对应了一条非树边或多条非树边。
我们把只经过一条非树边的奇圈称为主奇圈。
我们来寻找一条边 $e$ 能够删除的充要条件。
若 $e$ 为非树边，则能够删除的充要条件为，它在一个主奇圈上，且只有一个主奇圈。
必要性：显然。
充分性：若删除后还有奇圈，则一定不是主奇圈。而任何一个非主奇圈在 dfs 树上都能对应到一段链上，从而对应到至少一条在主奇圈上的边 $e'$，亦即，在删除 $e$ 之前，$e'$ 也在一个主奇圈上。
由假设，$e = e'$。因此不可能存在非主奇圈。
若 $e$ 为树边，则它能被删除的充要条件为，它在所有的主奇圈上，且不在任何一个主偶圈上。
必要性：显然。
充分性：若删除后还有奇圈，则如果这个奇圈对应的链不包含 $e$，那么可以找到一个不经过 $e$ 的主奇圈，矛盾。若包含 $e$，则可以找到经过 $e$ 的偶圈，均矛盾。
因此，我们需要统计的是，对于每条树边，有多少个主奇 (偶) 圈经过它。
由于每个主奇 (偶) 圈均对应一条非树边，因此每找到一条非树边 $e = (u, v)$，则给原树中连接 $u, v$ 的所有边经过的奇 (偶) 圈数增加 $1$。
可以看出，这是一个区间加，最后全局查询的问题。使用差分技术解决。
总时间复杂度 $O \left( n \right)$。
#include <bits/stdc++.h>
#define N 1000005
#define M 2000005
#define ad(x) ((x - 1 ^ 1) + 1)
int V, E, Es;
int to[M], first[N], next[M];
int tree_edge[M];
int p[N], dep[N], used[N];
int odd[N], even[N];
int eodd[M], eeven[M];
int odd_count = 0;
int ans_cnt = 0, ans[M];
inline void addedge(int u, int v){
to[++Es] = v; next[Es] = first[u]; first[u] = Es;
to[++Es] = u; next[Es] = first[v]; first[v] = Es;
}
void dfs(int x) {
int i, y;
for (i = first[x]; i; i = next[i])
if (p[y = to[i]] == -1) {
p[y] = x; dep[y] = dep[x] + 1;
tree_edge[i] = tree_edge[ad(i)] = 1;
dfs(y);
}
}
void dfs2(int x) {
int i, y; used[x] = 1;
for (i = first[x]; i; i = next[i])
if (p[y = to[i]] == x) {
dfs2(y);
odd[x] += odd[y]; even[x] += even[y];
eodd[i] = eodd[ad(i)] = odd[y];
eeven[i] = eeven[ad(i)] = even[y];
}
}
void output() {
printf("%d\n", ans_cnt);
for (int i = 1; i <= ans_cnt; ++i) printf("%d%c", ans[i], i == ans_cnt ? 10 : 32);
}
int main() {
int i, u, v;
scanf("%d%d", &V, &E);
for (i = 1; i <= E; ++i) scanf("%d%d", &u, &v), addedge(u, v);
memset(p, -1, sizeof p);
for (i = 1; i <= V; ++i)
if (p[i] == -1) p[i] = 0, dfs(i);
for (i = 1; i <= Es; i += 2)
if (!tree_edge[i]) {
u = to[i]; v = to[i + 1];
if (dep[u] < dep[v]) std::swap(u, v);
if ((dep[u] ^ dep[v]) & 1) ++even[u], --even[v]; // even cycle
else ++odd[u], --odd[v], ++odd_count, eodd[i] = eodd[ad(i)] = 1;
}
if (!odd_count) {
for (i = 1; i <= E; ++i) ans[++ans_cnt] = i;
output(); return 0;
}
for (i = 1; i <= V; ++i)
if (!used[i]) dfs2(i);
for (i = 1; i <= Es; i += 2)
if (tree_edge[i]) {
if (eodd[i] == odd_count && !eeven[i]) ans[++ans_cnt] = i + 1 >> 1;
} else {
if (eodd[i] && odd_count == 1) ans[++ans_cnt] = i + 1 >> 1;
}
output();
return 0;
}
坑1：统计经过一条边的主奇圈数时，不要忘记将它的对偶边也标记了。