传送门
思路：
依题意可知，在图中的每一条边有且只有一个点被选中（阻止老曹刷街），那么就可以对其采取二分图染色，一条边中：一个点为黑色，另一个点为白色；如果一条边中的两个端点的颜色相同，则说明无解，输出：“ Ipossible "；如果有解，就把白点的数目和黑点的数目取 min ，即为答案。
标程：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
using namespace std;
#define maxn 100100
int n,m,cnt,ans;
int head[maxn],col[maxn],tot[maxn],vis[maxn];
struct hh
{
int to,nex;
}t[maxn<<];
inline int read()
{
int kr=,xs=;
char ls;
ls=getchar();
while(!isdigit(ls))
{
if(!(ls^))
kr=-;
ls=getchar();
}
while(isdigit(ls))
{
xs=(xs<<)+(xs<<)+(ls^);
ls=getchar();
}
return xs*kr;
}
inline void add(int nex,int to)
{
t[++cnt].nex=head[nex];
t[cnt].to=to;
head[nex]=cnt;
}
inline bool dfs(int now,int c)//c为1，染上白点；c为0，染上黑点；now要被染色的点
{
vis[now]=true;col[now]=c;tot[c]++;//vis记录该点被染色过，col记录这个点染什么颜色
for(int i=head[now];i;i=t[i].nex)//跑遍这个连通块的所有点
{
int v=t[i].to;
if(vis[v]&&col[v]==col[now]) return false;
else if(!vis[v])
{
bool sign=dfs(v,(c+)&);//另一个端点染的颜色相反（黑→白，白→黑）
if(!sign) return false;
}
}
return true;
}
int main()
{
int x,y;
n=read();m=read();
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])//该连通块没被染过色
{
tot[]=tot[]=;//tot[0]为黑点，tot[1]为白点
bool sign=dfs(i,);//不仅能够判断有无解，还能染完总这个点起的连通块
if(!sign)//判断无解
{
printf("Impossible\n");
exit();//直接结束
}
else ans+=min(tot[],tot[]);//因为原图不连通，要加上所有连通块的答案。
}
}
printf("%d\n",ans);//输出
return ;
}