题意
sol
非常有思维含量的一道题,队爷的论文里介绍了一种(n sqrt{n})的暴力然鹅看不懂。。
看了一下clj的(o(nlogn))的题解,又翻了翻题交记录,发现(o(n))的做法也不是特别难。。
首先考虑所有两端颜色相同的非树边。直接对它的数量讨论:
若为(0),那么删哪一条都可以
若为(1),那么只能删该奇环上的边
若(>1),所有的非树边都不能删(不管怎么删都会有一个奇环),那么考虑所有的树边,一条树边能被删掉当且仅当:所有奇环都经过了这条边 且没有偶环经过了这条边
那么直接在树上打差分标记即可
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, pre[maxn], even[maxn], odd[maxn], col[maxn], cly, last, ans[maxn], dep[maxn]; struct edge { int u, v, id, nxt; }e[maxn]; int head[maxn], num; void addedge(int x, int y, int id) { e[num] = (edge) {x, y, id, head[x]}; head[x] = num++; } void dfs(int x, int fa) { col[x] = col[fa] ^ 1; dep[x] = dep[fa] + 1; for(int i = head[x]; ~i; i = e[i].nxt) { int to = e[i].v; if(col[to] == -1) { pre[to] = i; dfs(to, x); even[x] += even[to]; odd[x] += odd[to]; } else if(dep[to] + 1 < dep[x]){ if(col[to] == col[x]) last = i, cly++, odd[x]++, odd[to]--; else even[x]++, even[to]--; } } } int main() { memset(head, -1, sizeof(head)); n = read(); m = read(); for(int i = 1; i <= m; i++) { int x = read(), y = read(); addedge(x, y, i); addedge(y, x, i); } memset(col, -1, sizeof(col)); col[0] = 0; for(int i = 1; i <= n; i++) if(col[i] == -1) dfs(i, 0); if(cly == 0) { printf("%dn", m); for(int i = 1; i <= m; i++) printf("%d ", i); return 0; } if(cly == 1) ans[e[last].id] = 1; for(int i = 1; i <= n; i++) if(odd[i] == cly && !even[i]) ans[e[pre[i]].id] = 1; int cnt = 0; for(int i = 1; i <= m; i++) if(ans[i]) cnt++; printf("%dn", cnt); for(int i = 1; i <= m; i++) if(ans[i]) printf("%dn", i); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605493.html