题目大意：有n个点和m条路（双向），要你在某些点上放“河蟹”来“占领”这个点的所有路，但是任意两只河蟹不能放在有路径连接的两个点上，否则会打架，求最少多少只河蟹使得所有路全被占领，或者不可能全部占领。
算法：BFS（或DFS）染色
思路：因为BFS有分层效果，于是我使用BFS将每个联通块染成黑色和白色。如果两个相同颜色的点有路，说明不能放置河蟹，输出“Impossible”。否则对于每个联通块，算出黑、白各有几个点，取两者较小数加到答案中。所有联通块的点数之和即为答案。
此题数据规模较大，BFS时数组要开小点（内存越小速度似乎越快使用std::queue的请忽略），我丧心病狂地加了读优，加了inline，改了又改，最后数组减小改为循环队列，就过了……
没错就是这个点！！！
C++ Code:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#define C c=getchar()
using namespace std;
int n,m,cnt=0,ans=0,head[200050],next[200050],dist[200050],colour[10005],q[100005],st[100005];
inline int readint(){
int C;
while(!isdigit(c))C;
int p=0;
while(isdigit(c)){
p=p*10+c-'0';
C;
}
return p;
}
inline void ins(int x,int y){
cnt++;
next[cnt]=head[x];
head[x]=cnt;
dist[cnt]=y;
cnt++;
next[cnt]=head[y];
head[y]=cnt;
dist[cnt]=x;
}
void bfs(int begin){
memset(q,0,sizeof q);
memset(st,0,sizeof st);
int l=0,r=1;
q[1]=begin;
st[1]=1;
int f[2]={0,1};
colour[begin]=1;
while(l!=r){
l=(l+1)%100000;
int now=q[l];
for(int i=head[now];i;i=next[i]){
int t=dist[i];
if(colour[t]==-1){
colour[t]=(1+st[l])%2;
r=(r+1)%100000;
q[r]=t;
st[r]=st[l]+1;
f[colour[t]]++;
}else
if(colour[t]==colour[now]){
puts("Impossible");
exit(0);
}
}
}
ans+=(f[0]<f[1])?(f[0]):(f[1]);
}
int main(){
memset(next,0,sizeof next);
memset(colour,0xff,sizeof(colour));
memset(dist,0,sizeof dist);
n=readint(),m=readint();
for(int i=1;i<=m;i++){
int x,y;
x=readint(),y=readint();
ins(x,y);
}
for(int i=1;i<=n;i++)
if(colour[i]==-1)bfs(i);
printf("%d
",ans);
return 0;
}
----------------------------------------------------------2017.7.10----------------------------------------------------------
补充dfs的代码，思路与bfs一样，dfs是每搜一个换一种颜色。
重点在于，你看dfs的耗时与上面bfs的差距！！！
这差距也太大了吧！！
C++ Code：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#define C c=getchar()
using namespace std;
int n,m,cnt=0,ans=0,head[200050],next[200050],dist[200050],colour[10005];
int f[2];
inline int readint(){
int C;
while(!isdigit(c))C;
int p=0;
while(isdigit(c)){
p=p*10+c-'0';
C;
}
return p;
}
inline void ins(int x,int y){
cnt++;
next[cnt]=head[x];
head[x]=cnt;
dist[cnt]=y;
cnt++;
next[cnt]=head[y];
head[y]=cnt;
dist[cnt]=x;
}
void dfs(int begin,int co){
colour[begin]=co;
f[co]++;
for(int i=head[begin];i;i=next[i]){
if(colour[dist[i]]==-1)
dfs(dist[i],1-co);
else
if(colour[dist[i]]==co){
printf("Impossible
");
exit(0);
}
}
}
int main(){
memset(next,0,sizeof next);
memset(colour,0xff,sizeof(colour));
memset(dist,0,sizeof dist);
n=readint(),m=readint();
for(int i=1;i<=m;i++){
int x,y;
x=readint(),y=readint();
ins(x,y);
}
for(int i=1;i<=n;i++)
if(colour[i]==-1){
f[0]=f[1]=0;
dfs(i,0);
ans+=f[0]<f[1]?f[0]:f[1];
}
printf("%d
",ans);
return 0;
}