题目大意
给定一个 $n$ 个结点 $m$ 条边的无向联通图，问删去那些边后图是二分图。
$n, m \le 10^4$。
思路分析
图是二分图的充要条件是图中不存在长度为奇数的环。
无向图中的任意一个环都可以用 DFS 树上返祖边形成的环的 Xor 组成。
先搞出图的一棵 DFS 树，然后把返祖边构成的环拿出来。如果没有任何一个环长度为奇数的话，则所有边都可以删。
如果至少有一个奇环，则删去的边首先应该在这些环的交上，否则会有奇环出现。并且，它们不能被任意一个偶环所包含，否则它属于的一个奇环和那个偶环会形成一个新的奇环，即使删掉了这条边也无法清除奇环。
有了上述结论，我们就可以使用树上差分来解决问题了。时间复杂度 $O(n + m)$。
代码实现
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | |
6 | const int maxn = 1e4; |
7 | int n, m, k, a[maxn + 3], u[maxn + 3], v[maxn + 3], fa[maxn + 3], dep[maxn + 3], Co, Ce, So[maxn + 3], Se[maxn + 3]; |
8 | bool vis[maxn + 3]; |
9 | vector<int> G[maxn + 3]; |
10 | |
11 | void dfs(int u) { |
12 | vis[u] = true; |
13 | for (int i = 0, v; i < G[u].size(); i++) { |
14 | v = G[u][i]; |
15 | if (!vis[v]) { |
16 | fa[v] = u; |
17 | dep[v] = dep[u] + 1; |
18 | dfs(v); |
19 | } else if (v != fa[u] && dep[u] > dep[v]) { |
20 | int len = dep[u] - dep[v] + 1; |
21 | if (len & 1) { |
22 | Co++; |
23 | So[u]++, So[v]--; |
24 | } else { |
25 | Ce++; |
26 | Se[u]++, Se[v]--; |
27 | } |
28 | } |
29 | } |
30 | } |
31 | |
32 | void dfs_sum(int u) { |
33 | vis[u] = true; |
34 | for (int i = 0, v; i < G[u].size(); i++) { |
35 | v = G[u][i]; |
36 | if (!vis[v]) { |
37 | dfs_sum(v); |
38 | So[u] += So[v]; |
39 | Se[u] += Se[v]; |
40 | } |
41 | } |
42 | } |
43 | |
44 | int main() { |
45 | scanf("%d %d", &n, &m); |
46 | for (int i = 1; i <= m; i++) { |
47 | scanf("%d %d", &u[i], &v[i]); |
48 | G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]); |
49 | } |
50 | for (int i = 1; i <= n; i++) if (!vis[i]) { |
51 | dfs(i); |
52 | } |
53 | fill(vis + 1, vis + n + 1, false); |
54 | for (int i = 1; i <= n; i++) if (!vis[i]) { |
55 | dfs_sum(i); |
56 | } |
57 | for (int i = 1; i <= m; i++) { |
58 | if (dep[u[i]] < dep[v[i]]) { |
59 | swap(u[i], v[i]); |
60 | } |
61 | if (Co == 0 || (Co == 1 && dep[u[i]] != dep[v[i]] + 1 && (dep[u[i]] - dep[v[i]] + 1) & 1) || (dep[u[i]] == dep[v[i]] + 1 && So[u[i]] == Co && Se[u[i]] == 0)) { |
62 | a[++k] = i; |
63 | } |
64 | } |
65 | printf("%d\n", k); |
66 | for (int i = 1; i <= k; i++) { |
67 | printf("%d%c", a[i], " \n"[i == k]); |
68 | } |
69 | return 0; |
70 | } |