欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-07 07:54:05
题意 "题目链接" Sol 非常有思维含量的一道题,队爷的论文里介绍了一种$N \sqrt{N}$的暴力然鹅看不懂。。 看了一下clj的$O(nlogn)$的题解,又翻了翻题交记录,发现$O(n)$的做法也不是特别难。。 首先考虑所有两端颜色相同的非树边。直接对它的数量讨论: 若为$0$,那么删哪一 ......

题意

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;
}