题解：P14427 [JOISC 2014] 电压 / Voltage

· · 题解

题意即：给定一个无向图，问有多少条边 (u, v)，使得断开它后图是否是二分图，且 u, v 在图的同一部。

断开后是二分图的充要条件是，图中不存在奇环。所以 (u, v) 应该在所有奇环上。

综上，一条边符合条件当且仅当它在所有奇环上，且不在任何偶环上。

注意到这个只需考虑简单环，我们任取一颗 dfs 树做树上差分即可。

其实有一些简单环没有考虑到，即包含两条及以上返祖边的简单环。

考虑只有一条返祖边的 dfs 树所有奇环中树边的交是一条自上向下的路径（或者只有一个奇环的时候是一条链）。这条路径上没有连出返祖边，所以只要经过一次就会全部经过。两条奇环中的返祖边可以加一些树边组成奇环或偶环，手玩一下可以发现，如果不经过交集中的边，只可能走出偶环，否则会走出奇环。

奇环与偶环中的返祖边组合，以及偶环与偶环中的返祖边组合起来的情况类似。

可以发现这些信息都被标记过了，所以两条奇环中的返祖边组成的环全都没有用。于是只考虑 dfs 树上单条返祖边组成的环就是对的。

注意有一个 corner case：当奇环只有一个的时候，构成这个奇环的返祖边本身也一定满足条件，答案要加上 1。

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;

int n, m, a[N], b[N], head[N], dep[N], tag[2][N], tot = 1, cnt, ans;
vector<int> g[N];

struct edge
{
    int to, nxt;
} e[N << 1];

void addedge(int u, int v)
{
    e[++tot] = {v, head[u]};
    head[u] = tot;
}

void dfs(int u, int fa)
{
    for(int i = head[u]; i; i = e[i].nxt)
    {
        if(i == (fa ^ 1)) continue;
        int v = e[i].to;
        if(dep[v] && dep[v] < dep[u])
        {
            if((dep[u] - dep[v] + 1) & 1) tag[1][u]++, tag[1][v]--, cnt++;
            else tag[0][u]++, tag[0][v]--;
        }
        else if(!dep[v])
        {
            g[u].push_back(v);
            dep[v] = dep[u] + 1;
            dfs(v, i);
        }
    }
    return;
}

void dfs1(int u)
{
    for(auto v : g[u])
    {
        dfs1(v);
        tag[0][u] += tag[0][v];
        tag[1][u] += tag[1][v];
    }
    if(tag[1][u] == cnt && !tag[0][u] && dep[u] > 1) ans++;
    return;
}

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];
        addedge(a[i], b[i]);
        addedge(b[i], a[i]);
    }
    for(int i = 1; i <= n; i++)
        if(!dep[i]) dep[i] = 1, dfs(i, 0);
    for(int i = 1; i <= n; i++)
        if(dep[i] == 1) dfs1(i);
    cout << ans + (cnt == 1);
    return 0;
}