题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入输出格式
输入格式：第一行：两个整数N，M
接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式：仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
输入样例#1：
3 3
1 2
1 3
2 3
输出样例#1：
Impossible
输入样例#2：
3 2
1 2
2 3
输出样例#2：
1
说明
【数据规模】
1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
Solution：
由题意得每条边必须且有且只有一个顶点被封锁，即一条边所连向的两点不得同时被封锁，类似于二分图，so可以理解为对图染色，注意本图可能存在多个连通图，于是我们直接不停从没有被标记的点开始dfs并染色，使得相邻的点颜色不同，若某次访问到了被标记的点，则判断它的本次染色是否和本来颜色一致，不同则Impossible，否则答案就是每个连通图染色后最少的颜色个数的累加和。
代码：
#include<bits/stdc++.h> #define il inline #define ll long long #define N 200005 using namespace std; il int gi() { int a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')x=getchar(),f=1; while(x>='0'&&x<='9')a=a*10+x-48,x=getchar(); return f?-a:a; } int n,m,a,b,h[N],cnt,to[N],net[N],rs[N],sum[2],ans; bool vis[N]; il void add(int u,int v) { to[++cnt]=v,net[cnt]=h[u],h[u]=cnt; to[++cnt]=u,net[cnt]=h[v],h[v]=cnt; } il bool dfs(int x,int c) { if(vis[x]){return rs[x]==c?1:0;} vis[x]=1; sum[rs[x]=c]++; bool f=1; for(int i=h[x];i;i=net[i])f=f&&dfs(to[i],1-c); return f; } int main() { n=gi(),m=gi(); //memset(rs,-1,sizeof(rs)); int u,v; for(int i=1;i<=m;i++) { u=gi(),v=gi(); add(u,v); } for(int i=1;i<=n;i++) if(!vis[i]){ sum[0]=0;sum[1]=0; if(!dfs(i,0)){puts("Impossible");return 0;} ans+=min(sum[0],sum[1]); } cout<<ans; return 0; }