二分图染色

#include <bits/stdc++.h>
using namespace std;

const int kMaxN = 10000 + 5;
const int kMaxM = 100000 + 5;

int n, m;
struct Edge {
	int from;
	int to;
	int nxt;
} e[kMaxM * 2];
int tot, head[kMaxN];
void Add(int x, int y) {
	e[++tot] = (Edge){x, y, head[x]};
	head[x] = tot;
} 

int cnt1, cnt2;
int ans;
bool vis[kMaxN];
bool col[kMaxN];

void dfs(int x) {
	vis[x] = 1;
	cnt1 = cnt1 + col[x];
	cnt2 = cnt2 + (!col[x]);
	for (int i = head[x]; i != 0; i = e[i].nxt) {
		int to = e[i].to;
		if (vis[to] == 1 && col[to] == col[x]) {
			cout << "Impossible" << endl;
			exit(0);
		}
		else if (vis[to] == 1 && col[to] != col[x]) {
			return;
		}
		else {
			col[to] = (!col[x]);
			dfs(to);
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		Add(x, y);
		Add(y, x);
	}
	
	for (int i = 1; i <= n; i++) {
		cnt1 = 0;
		cnt2 = 0;
		if (!vis[i]) {
			dfs(i);
		}
		ans = ans + min(cnt1, cnt2);
	}
	
	cout << ans << endl;
  return 0;
}

记录

感激不尽！！！