@[Faith_toChange](/user/374769) 您需要对于每个连通块,将 `min(cnt[0], cnt[1])` 加进答案里,而不是全都统计完再取 min。
附改动后的 AC 代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
int n, m, head[maxn], tot, color[maxn], vis[maxn], cnt[maxn], ans;
struct Edge {
int v, to;
} e[maxn << 1];
inline void addedge(int u, int v) {
e[++tot] = {v, head[u]};
head[u] = tot;
}
bool dfs(int u, bool c) {
color[u] = c, vis[u] = true, cnt[c]++;
for (int i = head[u]; i; i = e[i].to) {
int v = e[i].v;
if (vis[v]) {
if (color[u] == color[v]) return false;
continue;
}
if (!dfs(v, c == 0)) return false;
}
return true;
}
signed main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
addedge(u, v), addedge(v, u);
}
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
cnt[0] = cnt[1] = 0;
if (dfs(i, 0) == false) {
cout << "Impossible" << endl;
return 0;
}
ans += min(cnt[0], cnt[1]);
}
cout<<ans<<endl;
return 0;
}
```
by M1rac0 @ 2023-01-01 23:58:42
@[tratser](/user/709949) 明白了,感谢!
by Faith_toChange @ 2023-01-02 08:02:44