*阳光大学
题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定*阳光大学，不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行*，当某个点被*后，与这个点相连的道路就被*了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹*了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以*所有道路并且不发生冲突。
输入输出格式
输入格式：
第一行：两个整数N，M
接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式：
仅一行：如果河蟹无法*所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
说明
【数据规模】
1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
分析：
思路非常巧妙的一道图论题，也是理解染色问题的一道好题。
首先，题目并没有保证是一个连通图，但经过分析也可以知道，只要每个子连通图都满足要求即可。重点在于，题目要求每一条边的连个端点必须有且仅有一个端点被占。那么实际上也就等效于，任意两个相邻的点必须被染成不同的颜色。那么思路有了就好做了，直接深搜或者广搜都行，遍历每个子连通图判断是否可以按照该原则染色即可。具体看代码。
Code：
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+;
const int M=1e5+;
bool vis[N];
int n,m,head[N],size,col[N],sum[],ans;
struct Node{int to,next;}edge[M<<];
inline int read()
{
char ch=getchar();int num=;bool flag=false;
while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}
while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}
return flag?-num:num;
}
inline void add(int x,int y)
{
edge[++size].to=y;
edge[size].next=head[x];
head[x]=size;
}
inline bool dfs(int u,int color)
{
if(vis[u]){
if(col[u]==color)return true;
return false;}
vis[u]=true;sum[col[u]=color]++;
bool flag=true;
for(int i=head[u];i!=-;i=edge[i].next){
flag=flag&&dfs(edge[i].to,-color);}
return flag;
}
int main()
{
memset(head,-,sizeof(head));
memset(vis,false,sizeof(vis));
n=read();m=read();int x,y;
for(int i=;i<=m;i++){
x=read();y=read();
add(x,y);add(y,x);}
for(int i=;i<=n;i++){
if(vis[i])continue;
sum[]=sum[]=;
if(!dfs(i,)){
printf("Impossible");
return ;}
ans+=min(sum[],sum[]);}
printf("%d",ans);
return ;
}