P1330 封锁阳光大学
大意
选择一部分点，使得与这个点相连的边全部被 \(\text{false}\) 掉，但是你选的点不能是相邻的点，输出最少方案数或者不可行。
思路
经典的二分图染色问题，对于每个连通块染色，选少的染，如果染不成了一定无解。
代码
#include<iostream>
#include<vector>
using namespace std;const int MAXN = 1e4 + 5;
int n, m;
int color[MAXN];
vector<int> g[MAXN];int a1 = 0, a2 = 0, ans = 0;bool dfs(int u, int col){color[u] = col;if(col == 1) a1 ++;else{a2 ++;}for(int i = 0;i < g[u].size();i ++){int v = g[u][i];if(!color[v]){if(!dfs(v, 3 - col)){return false;}}else if(color[v] == col){return false;}}return true;
}bool judge(){for(int i = 1;i <= n;i ++){if(!color[i]){a1 = 0, a2 = 0;if(!dfs(i, 1)){return false;}ans += min(a1, a2);}}return true;
}int main(){cin >> n >> m;for(int i = 1;i <= m;i ++){int u, v; cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}if(judge()){cout << ans << '\n';}else{cout << "Impossible\n";}return 0;
}