P1330 封锁阳光大学

普通的bfs染色问题

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
vector<int> vt[N];//存图
int n, m, vis[N], ans;

void bfs(int x, int a = 0, int b = 0) {
    queue<int> q;
    q.push(x), vis[x] = 1, a++;//vis的-1或1代表染色，哪种小取哪个
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (auto item: vt[now]) {
            if (vis[item] == 0)
                vis[item] = -vis[now], q.push(item), vis[item] == 1 ? a++ : b++;
            else if (vis[item] == vis[now]) {
                cout << "Impossible" << endl;
                exit(0);
            } else if (vis[item] == -vis[now]) continue;
        }
    }
    ans += min(a, b);
}


signed main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; cin >> u >> v, vt[u].push_back(v), vt[v].push_back(u), ++i);
    for (int i = 1; i <= n; vis[i] == 0 ? (bfs(i), 0) : 0, ++i);
    cout << ans << endl;
    return 0;
}