CF19E Fairy 题解

题意：

给定 \(n\) 个点，\(m\) 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。

输入格式：

第一行包含两个正整数 \(n,m~(n,m\le10^6)\)，分别表示点数和边数。

第 \(2\sim m+1\) 行，每行两个正整数 \(x,y~(1 \le x,y \le n,~x\ne y)\)，表示有一条 \((x,y)\) 的边。

输出格式：

第一行输出一个整数，表示能删除的边的个数。

第二行按照从小到大的顺序输出能删除的边的序号。

首先，一个图是二分图当且仅当图中没有奇数长度的环，即没有奇环。

那么我们只需要找到一些边，使得整个图删掉这些边以后没有奇环即可。

考虑建出原图的 DFS 树，则每个奇环对应了一条或多条非树边。

考虑只有一条非树边的奇环，不妨称之为主奇环。

结论1 若 \(e\) 为非树边，则 \(e\) 能被删除的当且仅当它位于（且仅位于）一个主奇环上。

证明必要性显然，考虑证明充分性。

根据假设，若删除后还有奇环，则一定不是主奇环。

而任何一个非主奇环在 DFS 树上都能对应到一段链，从而至少对应到另一条非树边 \(e'\) 。

即在删除 \(e\) 之前，\(e'\) 也在一个主奇环上。由假设可知 \(e=e'\) ，故不可能存在非主奇环。\(\square\)

结论2 若 \(e\) 为树边，则 \(e\) 能被删除的当且仅当它在所有的主奇环上，且不在任何一个主偶环上。

证明必要性显然，考虑证明充分性。

若删除后还有奇环，则

若这个奇环对应的链不包含 \(e\) ，那么可以找到一个不经过 \(e\) 的主奇环，矛盾。

若这个奇环对应的链包含 \(e\) ，那么可以找到经过 \(e\) 的主偶环，也矛盾。\(\square\)

那么我们需要统计的是，对于每条树边，有多少个主奇环/主偶环经过它。

由于每条主奇环/主偶环均对应一条非树边 \(e=(u,v)\) ，而 \(u\leadsto v\) 的每个节点都会得到 \(1\) 的贡献。

于是就变成了一个链上区间加，全局查询的问题了。考虑差分即可。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))
#define M ((int)(2e6 + 15))

bool tree_edge[M], vis[N];
int n, m, pos = 1, fa[N], dep[N], head[N];
int odd_cnt, ans_cnt, ans[N], odd[N], even[N], eodd[M], eeven[M];
struct Edge { int v, next; } e[M];
void addEdge(int u, int v) {  e[++pos] = {v, head[u]}; head[u] = pos; }
void dfs(int u)
{
    for(int i = head[u]; i; i = e[i].next)
    {
        const int &v = e[i].v;
        if(!~fa[v])
        {
            fa[v] = u; dep[v] = dep[u] + 1;
            tree_edge[i] = tree_edge[i ^ 1] = true; dfs(v); 
        }
    }
}
void dfs2(int u)
{
    vis[u] = true;
    for(int i = head[u]; i; i = e[i].next)
    {
        const int &v = e[i].v;
        if(fa[v] == u)
        {
            dfs2(v); odd[u] += odd[v]; even[u] += even[v];
            eodd[i] = eodd[i ^ 1] = odd[v];
            eeven[i] = eeven[i ^ 1] = even[v];
        }
    }
}
void output()
{
    cout << ans_cnt << '\n';
    rep(i, 1, ans_cnt) cout << ans[i] << " \n"[i == ans_cnt];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rep(i, 1, m)
    {
        static int u, v; cin >> u >> v;
        addEdge(u, v); addEdge(v, u);
    }
    memset(fa, -1, sizeof(fa));
    rep(i, 1, n) if(!~fa[i]) { fa[i] = 0; dfs(i); }
    for(int i = 2; i <= pos; i += 2)
    {
        if(!tree_edge[i])
        {
            int u = e[i].v, v = e[i + 1].v;
            if(dep[u] < dep[v]) swap(u, v);
            if((dep[u] ^ dep[v]) & 1) { ++even[u], --even[v]; }
            else { ++odd[u], --odd[v], ++odd_cnt, eodd[i] = eodd[i ^ 1] = true; }
        }
    }
    if(!odd_cnt) { rep(i, 1, m) ans[++ans_cnt] = i; output(); return 0; }
    rep(i, 1, n) if(!vis[i]) dfs2(i);
    for(int i = 2; i <= pos; i += 2)
    {
        if(tree_edge[i]) {
            if(eodd[i] == odd_cnt && !eeven[i]) ans[++ans_cnt] = (i + 1) / 2;
        } else {
            if(eodd[i] && odd_cnt == 1) ans[++ans_cnt] = (i + 1) / 2;
        }
    }
    return output(), 0;
}