cf19E. Fairy(奇环 二分图染色)

题意

题目链接

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("%d\n", 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("%d\n", cnt);

    for(int i = 1; i <= M; i++) if(ans[i]) printf("%d\n", i);

    return 0;

}