题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由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，任意两点之间最多有一条道路。
题解
这题是洛谷试炼场“图的遍历”的第二题。
这题是一道染色问题，本身很简单，难就难在这图不连通。
这里提供的做法是看题解之后写的，包括一些小技巧也是。
做法：通俗来说，就是，选点，然后一层层染色。具体实现就是遍历每一个点，如果它没有染过色，就从它开始，向它的相邻的点扩展染色，每染一层就让层数index++（在这个过程中，如果碰到两个同层的点相邻，就说明无法完成，就跳出循环），然后用两个数来记录奇偶两种方法的花费，取较小值返回，加到答案里。遍历完所有点，输出。如果中间有某个点无法完成，就输出Impossible。
注意：一定开足数组，还有，这是无向图。
时间：近似O(n)吧。
下来贴代码：
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
using namespace std;
struct edge{
int to,next;
}e[200001];
int n,m,tot;
int head[10001];
int vis[10001];
queue<int> q;
void addedge(int x,int y){
tot++;
e[tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
int bfs(int s){
q.push(s);
int index=1;
vis[s]=index;
int dan=0;
int all=0;
while(!q.empty()){
index++;
int k=q.size();
for(int i=0;i<k;i++){
int t=q.front();
q.pop();
vis[t]=index;
for(int j=head[t];j!=0;j=e[j].next){
int tar=e[j].to;
if(!vis[tar]){
q.push(tar);
}
else{
if(vis[tar]!=vis[t]){
continue;
}
return -1;
}
}
}
if(index&1){
dan+=k;
}
all+=k;
}
return min(dan,all-dan);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d %d",&x,&y);
addedge(x,y);
addedge(y,x);
}
int sum=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
int num=bfs(i);
if(num==-1){
printf("Impossible");
return 0;
}
sum+=num;
}
}
printf("%d",sum);
return 0;
}