求调教

#include<bits/stdc++.h>
using namespace std; // 采用 邻接表存储 因为是稀疏矩阵 
const int N = 100010,M = 200010; // 存 点 和 边 
int n, m;// 点 和 边 
int h[N], e[M], ne[M], idx; // ne 表示下一个点的编号 n 表示这个点所代表的值 idx 编号 
int color[N]; // 染色数组 
int vis[N], linkx[N];

void add(int a,int b){
	e[idx] = b,ne[idx] = h[a],h[a] = idx ++; // a 表示这个点, 在这个点插入点 
}

bool dfs(int u,int c){ // u 表示这个点 c 表示点的颜色 
	color[u] = c; // 染色操作 
	
	for (int i = h[u];i != -1; i = ne[i]){
		int j = e[i]; // 经典遍历链表操作 
		
		if (!color[j]){ // 没染色就染 3 - c 可以做到 1 2 的切换 
			if (!dfs(j, 3 - c)) return false; // 遍历到最后颜色相同就返回 false, 一直向前返回 false 
		}else if (color[j] == c) return false; // 只要一次 false 之后都 false, 一个奇数环都不能出现 
	}
	return true;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	memset(h, -1, sizeof(h));//链表初始化 
	while (m --){
		int a, b; // 将边加入邻接表(无向边) 
		cin >> a >> b;
		add(a, b), add(b, a);
	}
	bool flag = true; // 做标记 
	for (int i = 1; i <= n; i ++){
		if (!color[i]){ // 若没有被染色 则深搜染色 用 for 循环遍历每个点 防止出现 单个点的情况 
			if (!dfs(i,1)){ // 进入深搜 dfs(点编号, 染色编号) 没矛盾返回正确, 有矛盾返回 false
				// 这里用！便于运算 
				flag = false; // 表示没染对 
				break;
			}
		}
	}
	int ans = 0;
	if (!flag){ cout << "Impossible\n"; return 0;}
	else {
		int t = 0;
		for (int i = 1; i <= n; i ++) if (color[i] == 1) t ++;
		ans = min(t, n - t);
	}
	printf("%d", ans);
	return 0;
	
}