Codeforces Round #133 (Div. 2) B : Forming Teams

問題概要

頂点数V(<100)の最大次数2以下の無向グラフが与えられる。いくつかのノードを選んで、隣接するノードの色が異なるように2色で塗る。このとき各色の個数は等しくなければならない。色のついてないノードの最小個数を求める問題。

解法

最大次数2以下と聞いた瞬間に線か環になることに気づくので、後は奇数長の閉路の個数+(残りの点数)%2が答になる。

acceptされたコード

間違ってるわけじゃないけど補で考えている分無駄に複雑なことをしている。

#include <cstdio>
#include <vector>
using namespace std;


const int MAX_N = 100;

int N, M;
Graph G;
bool IS_LINE;
bool visited[MAX_N];

void init() {
	scanf("%d%d", &N, &M);
	G.init(N);
	for (int _ = 0; _ < M; ++_) {
		int from, to;
		scanf("%d%d", &from, &to);
		--from; --to;
		G.addUndirectedEdge(from, to);
	}
}

int dfs(int v) {
	visited[v] = true;
	IS_LINE |= (int)G[v].size() == 1;
	int ret = 1;
	for (int i = 0; i < (int)G[v].size(); ++i) {
		const int u = G[v][i].to;
		if (!visited[u]) {
			ret += dfs(u);
		}
	}
	return ret;
}

int solve() {
	int ans = 0, res = 0;
	for (int v = 0; v < N; ++v) if (!visited[v]) {
		IS_LINE = false;
		int cnt = dfs(v);
		if (G[v].empty()) {
			++res;
			continue;
		}
		ans += cnt&~(1);
		if (IS_LINE) {
			res += cnt % 2;
		}
	}
	return N - (ans + (res&~(1)));
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}