P1330 封锁阳光大学

https://www.luogu.com.cn/problem/P1330

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;
int cnt[2];
int color[maxn];
vector<int> g[maxn];
int n, m;

int dfs(int u) {
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (color[v] == -1) {
            color[v] = (color[u] + 1) % 2;
            cnt[color[v]]++;
            dfs(v);
        } else if (color[u] == color[v]) {
            cout << "Impossible" << endl;
            exit(0);
        }
    }
    return min(cnt[0], cnt[1] + 1);
}

int main() {
    memset(color, -1, sizeof(color));
    /*-1表示没有染色，0表示白色，1表示黑色*/
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cnt[0] = cnt[1] = 0;
        if (color[i] == -1) {
            color[i] = 1;
            ans += dfs(i);
        }
    }
    cout << ans;
    return 0;
}