封锁阳光大学

洛谷-P1330-封锁阳光大学

实现

#include <iostream>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 10010, M = 100010;
struct edge {
    int to, next;
};
edge e[2 * M];
int idx, head[N];
int n, m;
int c[N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
int bfs (int s) {
    int c1 = 0, c2 = 0;
    c[s] = 1;
    ++ c1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to;
            if (c[to] == c[cur]) return inf;
            if (c[to] == 0) {
                c[to] = 3 - c[cur];
                c[to] == 1 ? ++ c1 : ++ c2;
                q.push(to);
            }
        }
    }
    return min(c1, c2);
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; ++ i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }

    int res = 0;
    for (int i = 1; i <= n; ++ i) {
        if (c[i] == 0) {
            int val = bfs(i);
            if (val == inf) {
                printf("Impossible");
                return 0;
            } else {
                res += val;
            }
        }
    }
    printf("%d", res);
    return 0;
}