题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由n个点构成的无向图，n个点由m条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这条路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻两个点时，他们就会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入格式
第一行两个正整数，表示节点数和边数。 接下来m行，每行两个整数u,v,表示点u和点v之间有道路相连。
输出格式
仅一行如果河蟹无法封锁所有道路，则输出 Impossible，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
输入 #1
3 3 1 2 1 3 2 3
输出 #1
Impossible
输入 #2
3 2 1 2 2 3
输出 #2
1
说明/提示
【数据规模】
对于 n<10^5,m<10^6 保证没有重边。
2只河蟹靠着会打架。离得太远又挡不住老曹。我们可以看出，一条路要有且只有1只河蟹。而且一个点有河蟹，和他直接连接的点就不能有河蟹。利用这一点，我们可以随便找一个点开始染色，而且有无河蟹的部分是可以反转的，所以我们只要用两个变量记录放了多少只河蟹就好。如果有情况违反了规则，就直接输出Impossible。最后比较一下2种颜色的点哪个少就输出哪个就好了。存图可以用之前说的链式前向星偶。
对了，因为是正反存图，所以数组要开到m的两倍大。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
long long head[30005],color[30005],bl,hs,bs,bj[30005],n,m,a1,a2,shu;
struct hehe
{
long long nxt,zd;
}a[300005];
int dfs(int wz,int ys,bool yl)
{
if(bj[wz]==1)
{
if(color[wz]==ys)
{
return true;
}
return false;
}
bj[wz]=1;
color[wz]=ys;
//cout<<wz<<" "<<ys<<endl;
if(ys==1)
{
hs++;
}else
{
bs++;
}
for(int i=head[wz];i!=0;i=a[i].nxt)
{
if(dfs(a[i].zd,1-ys,true)==false)
{
yl=false;
}
}
return yl;
}
void add(int qd,int zd)
{
bl++;
a[bl].nxt=head[qd];
a[bl].zd=zd;
head[qd]=bl;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>a1>>a2;
add(a1,a2);
add(a2,a1);
}
for(int i=1;i<=n;i++)
{
if(bj[i]==0)
{
hs=0;
bs=0;
if(dfs(i,0,true)==false)
{
cout<<"Impossible"<<endl;
return 0;
}
shu+=min(hs,bs);
}
}
cout<<shu<<endl;
return 0;
}
代码就这么结束了，大家自己试试吧。