题目大意
给你一个无向图, 问加入删除那一条边能让这个图是二分图。
解题报告
很好的题目, 环异或, 代码进行了一些蛇皮操作wa到失去信仰。
Hineven太懒了不写题解了…
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> #include <vector> using namespace std; int N, M; inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return flg ? -ret : ret; } const int MAXN = 10010; struct Node { int v, nxt, id; } d[MAXN*2]; int head[MAXN], etot; inline void addEdge (int a, int b, int id) { //printf("edge:%d->%d\n", a, b); etot ++; d[etot].v = b; d[etot].nxt = head[a]; d[etot].id = id; head[a] = etot; } int pfa[MAXN]; inline int root (int u) {return pfa[u] ? pfa[u] = root(pfa[u]) : u;} int inp[MAXN][2]; bool used[MAXN]; int fa[MAXN], dep[MAXN], sz[MAXN], top[MAXN]; int dfn[MAXN], lst[MAXN], dfntot; void dfsSize (int u, int f) { sz[u] = 1; for(int e = head[u]; e; e = d[e].nxt) { if(d[e].v == f) continue ; dfsSize(d[e].v, u); sz[u] += sz[d[e].v]; } } void dfsChain (int u, int f) { dfn[u] = ++dfntot; int mxp = 0; if(!top[u]) top[u] = u; fa[u] = f, dep[u] = dep[f]+1; for(int e = head[u]; e; e = d[e].nxt) { if(d[e].v == f) continue ; if(sz[d[e].v] > sz[mxp]) mxp = d[e].v; } if(!mxp) {lst[u] = dfntot; return ;} top[mxp] = top[u], dfsChain(mxp, u); for(int e = head[u]; e; e = d[e].nxt) if(d[e].v != f && d[e].v != mxp) dfsChain(d[e].v, u); lst[u] = dfntot; } inline int getLCA (int a, int b) { while(top[a] != top[b]) { if(dep[top[a]] > dep[top[b]]) a = fa[top[a]]; else b = fa[top[b]]; } return dep[a] > dep[b] ? b : a; } struct BArr { int C[MAXN]; inline int lowbit (int a) {return a&-a;} inline void add (int p, int val) { while(p <= dfntot) C[p] += val, p += lowbit(p); } inline int query (int p) { int ret = 0; while(p) ret += C[p], p -= lowbit(p); return ret; } } circ[2]; vector<int> ans; int lst_rec[MAXN], cir_cnt[MAXN]; int main () { N = getInt(), M = getInt(); for(int i = 1; i<=M; i++) { int a = getInt(), b = getInt(); inp[i][0] = a, inp[i][1] = b; } for(int i = 1; i<=M; i++) { int a, b; int ra = root(a = inp[i][0]), rb = root(b = inp[i][1]); if(ra != rb) { used[i] = true; addEdge(a, b, i), addEdge(b, a, i); pfa[ra] = rb; } } for(int i = 1; i<=N; i++) if(!sz[i]) dfsSize(i, 0), dfsChain(i, 0); // not guaranteed connected graph int hcnt = 0; for(int i = 1; i<=M; i++) { if(used[i]) continue ; int a = inp[i][0], b = inp[i][1]; int lca = getLCA(a, b); int cur = (dep[a]+dep[b]+1-dep[lca]*2)&1; if(cur == 1) { hcnt += (cir_cnt[root(a)] == 0); cir_cnt[root(a)]++; lst_rec[root(a)] = i; } circ[cur].add(dfn[lca], -2); circ[cur].add(dfn[a], 1), circ[cur].add(dfn[b], 1); } if(hcnt > 1) {puts("0"); return 0;} if(hcnt == 0) for(int i = 1; i<=M; i++) ans.push_back(i); else { int p; for(int i = 1; i<=N; i++) if(cir_cnt[root(i)]) {p = root(i); break;} if(cir_cnt[p] == 1) ans.push_back(lst_rec[p]); for(int i = 1; i<=M; i++) { if(!used[i]) continue ; int a = inp[i][0], b = inp[i][1]; if(root(a) != p) continue ; if(dep[a] < dep[b]) swap(a, b); if((circ[1].query(lst[a])-circ[1].query(dfn[a]-1) == cir_cnt[p]) && (circ[0].query(lst[a])-circ[0].query(dfn[a]-1) == 0)) ans.push_back(i); } } sort(ans.begin(), ans.end()); printf("%d\n", ans.size()); for(int i = 0; i<(int)ans.size(); i++) printf("%d%c", ans[i], (i == (int)ans.size()-1) ? '\n' : ' '); }
Join the discussion