题目大意：给定一个 N 个点，M 条边的无向图，现在要选出图中的一个顶点集合，使得集合种的顶点不直接相邻，且这张图的所有边都被该顶点集合覆盖，求该顶点集合大小的最小值，若不能完成覆盖，则输出 impossible。
题解：由于要求集合中顶点不能相邻，且每条边都要被覆盖，则对于任意一条边来说，连接该边的两个顶点必有且只有一个在该集合中。对于这种相邻顶点不能在同一个集合中的性质，可以考虑对图进行染色的操作，即：相邻顶点的颜色不同，看是否可以用两个颜色染完整张图而不发生冲突，染色时顺便记录下每种颜色的顶点个数，个数少的即为答案贡献的一部分。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxv=1e4+10;
const int maxe=1e5+10;
inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
struct node{
int nxt,to;
}e[maxe<<1];
int tot=1,head[maxv];
int n,m,ans,sum[2];
bool vis[maxv],cor[maxv];
inline void add_edge(int from,int to){
e[++tot]=node{head[from],to},head[from]=tot;
}
void read_and_parse(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int from=read(),to=read();
add_edge(from,to),add_edge(to,from);
}
}
bool dfs(int u,int c){
if(vis[u])return cor[u]==c;
vis[u]=1,++sum[cor[u]=c];
for(int i=head[u];i;i=e[i].nxt)if(!dfs(e[i].to,c^1))return 0;
return 1;
}
void solve(){
for(int i=1;i<=n;i++)if(!cor[i]){
sum[0]=sum[1]=0;
if(!dfs(i,0)){puts("Impossible");return;}
ans+=min(sum[0],sum[1]);
}
printf("%d\n",ans);
}
int main(){
read_and_parse();
solve();
return 0;
}