题面
给定 \(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;
}