传送门：P1330 封锁阳光大学
更佳的阅读体验：洛谷 P1330 题解

阅读本文前，请确保你已经对二分图有所了解。

简要题意：给你一张无向图，求最少选取的节点数量，使得节点之间两两不相邻，且每条边都连接着一个选中节点。

观察给出的条件，发现每个点只有“选”或“不选”两种对立的状态，并且相邻节点的状态必须是不同的。由此我们想到，本题事实上是要求我们判断给定图是否为二分图，因此可以直接染色。

如果染色过程中发现了冲突，说明给定图不是二分图，不论如何也无法得到任何一种合法的方案，此时直接输出 $\texttt{Impossible}$ 并退出程序即可。染色结束后，我们取两种颜色中较少的节点数作为答案即可。

你兴高采烈地写出了一份朴素的二分图染色，然后得到了 50 分的好成绩。

此时你发现，题目给出的限制中，只保证了给定图是一张无向图，而非无向连通图。这样的话，我们就应当对每个连通块进行讨论了。对于每个连通块，我们仍然取两种颜色中较少的节点数，答案即为每个连通块的答案之和。

时间复杂度 $O(n + m)$。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e4 + 10;
int n, m, u, v, col[N], cnt[2], ans;
basic_string<int> g[N];

void dfs(int u, int c) {
    col[u] = c, ++cnt[c];
    for (auto v : g[u]) {
        if (col[v] != -1) {
            if (col[v] == col[u]) {
                cout << "Impossible\n";
                exit(0);
            } continue;
        } dfs(v, c ^ 1);
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v;
        g[u] += v, g[v] += u;
    } fill(col + 1, col + n + 1, -1);
    for (int i = 1; i <= n; ++i) if (col[i] == -1) {
        cnt[0] = cnt[1] = 0;
        dfs(i, 0);
        ans += min(cnt[0], cnt[1]);
    } cout << ans << '\n';
    return 0;
}