读书人的事情，那能叫刷街吗？
——《孔乙己》

题意描述：

（唐）曹是一只爱刷街的老（唐）曹……

暑假期间，他每天都欢快地在阳光大学的校园里刷街。

河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹（唐）刷街。

阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。

每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹（唐）就无法在与这些道路上刷街了。

但非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

现在问题来了：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

输入格式：

第一行：两个整数N，M

接下来M行，每行两个整数A，B，表示点A到点B之间有道路相连。

输出格式：

仅输出一行

如果河蟹无法封锁所有道路，则输出一个字符串“Impossible”

否则输出一个整数，表示最少需要多少只河蟹

Input & Output ‘s examples

Input ‘s eg 1

3 3
1 2
1 3
2 3

Output ‘s eg 1

Impossible

Input ‘s eg 2

3 3
1 2
2 3

Output ‘s eg 2

1

分析

一道好题，如果有思路的话还是很好写的。

下面，我们就来分析几种做法。

枚举

首先，你可能本着枚举法无敌论的原则选择枚举

但是……

超高的时间复杂度会让你呕吐的

我们可以分析一下，假设这张图是有解的，那么枚举一定会枚举出所有Impossible的情况才能确定有解。

而Impossible的数量与点数有关，如果大一点，就可能有上百万种……（这就是为什么暴力比正解还难写）

因此，枚举是不可以的

直接dfs & bfs

同理，会被卡死在时间复杂度上，不多解释（其实是作者太懒了……）

正解

很显然，这是一个非连通图，所以我们可以把它拆成许多个连通子图来做

多读几遍题目，不难发现两个关键点：

1.每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了
2.当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

翻译成人话就是

一条边的两个端点上 必须有 且 只有一个端点 上有河蟹

是不是明白了什么？

这就是一道二分图染色题啊！（ps.即把相邻的两个点染成不同的颜色）

对于一张连通子图，只有三种染色情况，分别是color1 ，color2和Impossible

所以，我们把所有子图染一遍色，如果有一个为Impossible就输出答案，如果没有，就把结果加起来取min即可

是不是很简单啊（逃）~

附件（AC标程，防作弊已开启）

#include<iostream>
#include<algorithm>
#define N 100001

using namespace std;

struct Edge{
	int to;
	int last;	//一只可爱的链式前向星 
}edge[N];

int end[N];
int edge_number;

void add_edge(int from , int to){
	edge[++edge_number].to = to;
	edge[edge_number].last = end[from];
	end[from] = edge_number;
}

int ans;		//最后的答案 
int color[N];	//表示该点的颜色 
bool visit[N];	//表示该点是否染过色
int number[2];	//表示该颜色的点的数量 


bool draw(int s , int color2){	//color2表示该点染成的颜色,返回的如果为false，则为Impossible 
	if(visit[s]){
		if(color[s] == color2){
			return true;
		}//特判，如果该点染过色，就判断染得颜色是否与本次的一致 
		else{
			return false;
		}
	}
	visit[s] = true;
	color[s] = color2;	//给该点染色 
	number[color2] ++;	//该颜色的点数量+1 
	bool p = true;
	for(int i = end[s]; i != 0 && p != 0; i = edge[i].last){
		p = p && draw(edge[i].to , !color2);	//判断与另一端点是否冲突 
	}
	return p;
}

void work(int ans){
	ans+= 1;
}

int n , m;

int main(){
	int a , b;
	cin >> n >> m;
	for(int i = 1; i <= m; i ++){
		cin >> a >> b;
		add_edge(a , b);
		add_edge(b , a);
	} 
	for(int i = 1; i <= n; i ++){
		if(visit[i] == true){
			continue;
		}
		number[0] = 0;//每次清空该颜色的数量 
		number[1] = 0;
		if(!draw(i , 0)){
			cout << "Impossible" <<endl;
			return 0;
		}
		ans = ans + min(number[0] , number[1]);
	} 
	work(ans);
	cout << ans <<endl;
	
	return 0;
}

THE END