【题解】Cf19E Fairy 树上瞎搞 BZOJ – 4424

题目链接：https://www.mina.moe/BZPRO/JudgeOnline/4424.html

题目大意：给定 n 个点，m 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成
一个二分图。

考场上我看到就懵逼了——虽然我的确知道一个图是二分图的充要条件是没有奇环，但是我没有想到能用生成树来搞。

首先 Dfs 随机一棵生成树（严格地说是森林）

然后除了树边就只有返祖边了（当然子树与子树之间是一定没有边的）

每一条返祖边就代表一个环嘛，而且你能轻松算出这个环的奇偶性。

如果不存在奇环——皆大欢喜，你可以删除任意一条边。

如果不是就需要讨论一下：

• 对于一条树边，如果经过它的奇环个数等于总奇环个数，且没有偶环经过它，那删除它就一定可以清除所有奇环。不能有偶环经过它是因为如果又有奇环经过它又有偶环经过它，那么删除它会导致奇环于偶环结合构成新的奇环
• 对于一条非树边，如果奇环总共只有一个，且这个奇环经过它，那删除它是可以清除掉这个奇环的，否则一定不能清除所有奇环

这个统计环的数目用树上前缀和就行啦。

看来把图问题转化为树上问题也是不错的选择啊

代码：

#include <bits/stdc++.h>

#define NS (1000005)
#define MS (2000005)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m;

struct Graph
{
    int head[NS], nxt[MS], to[MS], c1[MS], c2[MS], sz; // c1: 奇环个数 c2: 偶环个数
    bool flag[MS];
    Graph() {memset(head, -1, sizeof(head)), sz = 0;}
    void push(int a, int b)
    {
        nxt[sz] = head[a], to[sz] = b, head[a] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g;

int dep[NS], c1[NS], c2[NS], odd_cnt; // c1: 奇环个数 c2: 偶环个数 odd_cnt: 奇环总数

void Dfs(int a, int pre)
{
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (!dep[g[i]])
        {
            dep[g[i]] = dep[a] + 1, Dfs(g[i], i);
            c1[a] += c1[g[i]], c2[a] += c2[g[i]];
            g.c1[i] = c1[g[i]], g.c2[i] = c2[g[i]];
            g.flag[i] = 1;
        }
        else if (i != (pre ^ 1) && dep[g[i]] <= dep[a])
        {
            if (a == g[i]) // 特判自环，巨坑
            {
                if (i & 1) g.c1[i]++, odd_cnt++;
                continue;
            }
            if ((dep[a] - dep[g[i]]) & 1) c2[a]++, c2[g[i]]--, g.c2[i]++;
            else c1[a]++, c1[g[i]]--, g.c1[i]++, odd_cnt++;
        }
}

vector<int> ans;

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1, a, b; i <= m; i += 1)
        IN(a), IN(b), g.push(a, b), g.push(b, a);
    for (int i = 1; i <= n; i += 1) if (!dep[i]) dep[i] = 1, Dfs(i, -1);
    if (!odd_cnt)
    {
        printf("%d\n", m);
        for (int i = 1; i <= m; i += 1) printf("%d ", i);
        putchar(10);
        return 0;
    }
    for (int i = 0; i < g.sz; i += 1)
        if (g.flag[i])
        {
            if (!g.c2[i] && g.c1[i] == odd_cnt) ans.push_back((i >> 1) + 1);
        }
        else if (odd_cnt == 1 && g.c1[i]) ans.push_back((i >> 1) + 1);
    printf("%lu\n", ans.size());
    for (int i = 0; i < ans.size(); i += 1) printf("%d ", ans[i]);
    putchar(10);
    return 0;
}