https://www.luogu.com.cn/problem/P1330
题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由 n 个点构成的无向图，n 个点之间由 m 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入格式
第一行两个正整数，表示节点数和边数。 接下来 m 行，每行两个整数 u,v表示点 u 到点 v 之间有道路相连。
输出格式
仅一行如果河蟹无法封锁所有道路，则输出 Impossible，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
输入
3 3
1 2
1 3
2 3
输出
Impossible
输入
3 2
1 2
2 3
输出
1

二分图，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int n,m,x,y,ans,cnt,color[20*MAX];
struct Edge{
	int to,next;
}edge[20*MAX];
int head[MAX],tot;
void init(){
	tot=0;
	memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
bool dfs(int u){
	cnt ++;  //统计此联通块节点数目 
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v= edge[i].to; //枚举每条边 <u,v>
		if(color[u]==color[v]) return false; //节点 v 已着色，且和节点 u 的颜色冲突
		if(!color[v]){
			color[v]=3-color[u];     //给结点 v 着与结点 u 相反的颜色
			if(color[v]==1) ans ++;
			if(!dfs(v)) return false;
		}
	}
	return true;
}
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);
	init();
	while(m--){
		sf(x);sf(y);
		addedge(x,y);
		addedge(y,x);
	}
	mem(color,0);
	int _min = 0;
	fi(i,1,n+1){
		if(!color[i]){   // 非联通图，遍历所有节点
			ans =1;color[i]=1;cnt=0;   // cnt  当前连通块的节点个数
			if(dfs(i)){
				_min += min(ans,cnt-ans); //一种着色方案，颜色反转即另一种方案的结果
			}else {
				pfc("Impossible");
				return 0;
			}	
		}
	}
	pf(_min);
	return 0;
}