题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定*阳光大学，不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行*，当某个点被*后，与这个点相连的道路就被*了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹*了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以*所有道路并且不发生冲突。
输入输出格式
输入格式：
第一行：两个整数N，M
接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式：
仅一行：如果河蟹无法*所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
输入样例#1：
【输入样例1】
3 3
1 2
1 3
2 3 【输入样例2】
3 2
1 2
2 3
输出样例#1：
【输出样例1】
Impossible 【输出样例2】
1
说明
【数据规模】
1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
很裸的二分图染色
每个连通分量里选择节点数最少的颜色加上
不能染色就无解
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e4+,M=1e5+,INF=1e8+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,u,v,w;
struct edge{
int v,ne;
}e[M<<];
int h[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
int col[N],c1=,size=;
bool color(int u,int c){
size++;
if(c==) c1++;
col[u]=c;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(col[u]==col[v]) return false;
if(!col[v]&&!color(v,-c)) return false;
}
return true;
} int main(){
n=read();m=read();
for(int i=;i<=m;i++){
u=read();v=read();ins(u,v);ins(v,u);
}
int flag=,ans=;
for(int i=;i<=n;i++) if(!col[i]){
c1=size=;
if(!color(i,)){flag=;break;}
ans+=min(c1,size-c1);
}
if(flag) puts("Impossible");
else printf("%d",min(ans,n-ans));
}