题意：
无向图，给一个顶点染色可以让他相邻的路不能通过，但是相邻顶点不能染色，求是否可以让所有的路不通，如果可以求最小染色数。
思路：
对于无向图中的每一个连通子图，都只有两种染色方法，或者染不了，直接搜即可，注意搜的姿势
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<stack> #include<queue> #include<deque> #include<set> #include<vector> #include<map> #include<functional>#define fst first #define sc second #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lc root<<1 #define rc root<<1|1 #define lowbit(x) ((x)&(-x)) using namespace std;typedef double db; typedef long double ldb; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> PI; typedef pair<ll,ll> PLL;const db eps = 1e-6; const int mod = 1e9+7; const int maxn = 2e6+100; const int maxm = 2e6+100; const int inf = 0x3f3f3f3f; const db pi = acos(-1.0); vector<int>v[maxn]; int vis[maxn]; int c[maxn]; int sum[2]; bool dfs(int i, int cl){if(vis[i]==1){if(cl==c[i])return true;else return false;}vis[i] = 1;c[i] = cl;sum[cl]++;int sz = v[i].size();bool ans = true;for(int j = 0; j < sz; j++){ans = ans && dfs(v[i][j], cl^1);}return ans; } int main() {int n, m;scanf("%d %d", &n, &m);for(int i = 0; i < m; i++){int x, y;scanf("%d %d", &x, &y);v[x].pb(y);v[y].pb(x);}mem(vis, 0);int ans = 0;for(int i = 0; i < n; i++){if(vis[i]==1)continue;sum[0] = sum[1] = 0;if(!dfs(i, 0)){printf("Impossible");return 0;}ans += min(sum[0], sum[1]);}printf("%d", ans);return 0; } /* 4 2. 2 4 0 0 1 1 2 4 0 1 0 2 2 3 0 1 2 2 4 0 0 0 1 */
