RT

用的二分图方法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
int n, m, ans;
int ran[2], col[maxn];// col标记每个点的染色情况                     ran标记染0,1色点分别的个数 
int to[maxn], h[maxn], nxt[maxn], tot;
bool f; //标记
void add(int u, int v) {
	tot++;
	to[tot] = v;
	nxt[tot] = h[u];	
	h[u] = tot;
}
void dfs(int u){
	for(int i = h[u];i;i = nxt[i]) {
		int v = to[i];//将要染色的点 
		if(col[u] == col[v]){f = 1;break;}//颜色重复说明不符合二分图的定义，直接返回输出impossible 
		else if(col[v] == -1){
			col[v] = (col[u] + 1) % 2;//将要染色的点染色 
			ran[col[v]]++;//记录该颜色的点的总个数 
			dfs(v); 
		}
	}
}
int main() {
	cin >> n >> m;
	int a, b;
	for(int i = 1;i <= m;i++) {
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	f = false; 
	memset(col, -1, sizeof(ran));//将所有点的颜色全部标记成-1，表示没有染过色 
	for(int i = 1;i <= n;i++) {//开始染色 
		col[i] = 0;ran[0] = 1;ran[1] = 0;//将第i个点的颜色初始化成0 
		dfs(i);
		if(f){ans = -1;break;}
		ans += min(ran[0], ran[1]);
	}
	if(ans == -1)cout << "Impossible" << endl;
	else cout << ans << endl;
	return 0;
}