[Codeforces 19E] Fairy

题目大意

给你一个无向图, 问加入删除那一条边能让这个图是二分图。

解题报告

很好的题目, 环异或, 代码进行了一些蛇皮操作wa到失去信仰。

Hineven太懒了不写题解了…

Dad3zZ大佬的博客

代码

#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' : ' ');

}