描述 曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。 阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。 输入输出格式
输入格式： 第一行：两个整数N，M 接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式： 仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
输入样例： 【输入样例1】 3 3 1 2 1 3 2 3 【输入样例2】 3 2 1 2 2 3 输出样例： 【输出样例1】 Impossible 【输出样例2】 1 说明 【数据规模】 1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
题解：基本告别智商了，这种题目错了好几次。对于每一个单一的连通块独立求解，每个联通块内的点可以分为编号为1和-1的两种点，对于每个已经编号的点，所有与他相邻的点的编号都必须与他的不一样，如果有一样的话，就直接输出Impossible，最后判断一下这两种点哪种点数少，累加到答案中。
#include<iostream> #include<cstdio> #include<queue> #include<cstdlib> #include<cstring> #define LiangJiaJun main #define INF 1999122700 using namespace std; int a[100004],n,m,pom=0; int h[100004],ne=1; bool qq=1; struct edge{int to,next;}e[300004]; void insert(int u,int v){ e[++ne].to=v; e[ne].next=h[u]; h[u]=ne; } queue<int>q; bool bfs(int t){ a[t]=1;int sum=0,cnt=0; q.push(t); while(!q.empty()){ int x=q.front(); q.pop(); if(a[x]==1)sum++;cnt++; for(int i=h[x];i;i=e[i].next){ if(a[e[i].to]==0){ a[e[i].to]=a[x]*(-1); q.push(e[i].to); } else if(a[e[i].to]==a[x]){ qq=0; return puts("Impossible"); } } } pom+=min(sum,cnt-sum); } int LiangJiaJun(){ memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); insert(u,v);insert(v,u); } for(int i=1;i<=n;i++)if(!a[i]){ bfs(i);if(!qq)return 0; } printf("%d\n",pom); return 0; }