[JOISC 2014 Day3] 电压 题解

题面

给定 \(n\) 个点 \(m\) 条边的无向图。

现在要对每个点黑白染色。

若能够使一条边连接的两点颜色相同，其他边连接的两点颜色不同，则这条边合法。

求合法的边数。

$ 2 \leq n \leq 10^5,1 \leq m \leq 2 \times 10^5$。

图可能不连通，不保证没有重边。

题解

首先考虑转化一下题目条件，可以转化为删除一条边后剩余的边组成一个二分图，且该边连接的点在二分图的同一部。在此基础上经过分析可以得出偶环上的边均不合法，奇环上的边合法当且仅当其覆盖所有奇环。那么接下来的问题就转化成了统计每条边覆盖的偶环数和奇环数，以及整张图中的奇环数。

考虑环是如何产生的，发现在图的 DFS 生成树上每条返祖边均会产生环。所以考虑对于每条返祖边 \(\left(u, pa\right)\)，设其连接的两点在 DFS 生成树上的深度差为 \(\Delta = \operatorname{depth}_x - \operatorname{depth}_{pa}\)，那么环长显然为 \(len = \Delta + 1\)。所以这个返祖边覆盖的树边上都会覆盖一个对应的环，可以发现这个贡献是对一条链的贡献，故可以应用边差分解决。

接下来考虑如何统计答案，注意到统计的时候只会统计树边，也就是说返祖边不会被统计，下面讨论缺少的情况。

• 如果图中只存在一个奇环，那么这条边会产生贡献，判断出这种情况计算即可；

• 如果图中存在多于一个奇环，那么可以发现不存在一个返祖边存在于多个环中，也就是说返祖边一定不合法，不会产生贡献，故无需考虑。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;

valueType N, M, oddCount = 0;
bitset visited;
ValueVector depth, even, odd;
ValueMatrix G;

void dfs(valueType x, valueType from) {
    visited[x] = true;

    depth[x] = depth[from] + 1;

    bool first = true;

    for (auto const &iter: G[x]) {
        if (first && iter == from) {
            first = false;

            continue;
        }

        if (!visited[iter]) {
            dfs(iter, x);

            odd[x] += odd[iter];
            even[x] += even[iter];
        } else if (depth[iter] < depth[x]) {
            valueType const delta = depth[x] - depth[iter] + 1;

            if (delta & 1) {
                ++odd[x];
                --odd[iter];
                ++oddCount;
            } else {
                ++even[x];
                --even[iter];
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::cin >> N >> M;

    G.resize(N + 1);

    for (valueType i = 0; i < M; ++i) {
        valueType a, b;

        std::cin >> a >> b;

        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }

    depth.resize(N + 1, 0);
    even.resize(N + 1, 0);
    odd.resize(N + 1, 0);
    visited.resize(N + 1, false);

    for (valueType i = 1; i <= N; ++i)
        if (!visited[i])
            dfs(i, 0);

    valueType ans = 0;

    for (valueType i = 1; i <= N; ++i)
        if (depth[i] != 1 && even[i] == 0 && odd[i] == oddCount)
            ++ans;

    if (oddCount == 1)
        ++ans;

    std::cout << ans << std::endl;
}