1990.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1990 on 2006-07-24 at 09:45:25 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;
const int INF = 1 << 20;

bool dlk[N][N], vst[N], fg[N];
int n;

int dfs(int, bool);

int main()
{
	int m, i, j, k;
	bool sub[N];
	
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		memset(dlk, false,sizeof(dlk));
		for(i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b);
			dlk[a-1][b-1] = dlk[b-1][a-1] = true;
		}
		memset(vst, false, sizeof(vst)); memset(fg, false, sizeof(fg));
		int g[N], gn = 0;
		bool can = true;
		for(i = 0; i < n && can; i++) {
			if(vst[i]) continue;
			g[gn++] = abs(dfs(i, true));
			if(g[gn-1] > N) can = false;
		}
		if(!can) { printf("-1\n"); continue; }
		int stack[N], top = 0; stack[top++] = 0;
		for(i = 0; i < gn; i++) {
			memset(sub, false, sizeof(sub));
			int nxt[N], nn = 0;
			for(j = 0; j < top; j++)
				for(k = -1; k <= 1; k++) {
					if(k == 0) continue;
					int nk = abs(stack[j]+k*g[i]);
					if(sub[nk]) continue;
					sub[nk] = true; nxt[nn++] = nk;
				}
			memcpy(stack, nxt, sizeof(nxt)); top = nn;
		}
		for(i = 0; i < n; i++)
			if(sub[i]) break;
		printf("%d\n", i);
	}
	
	return 0;
}

int dfs(int o, bool isFg)
{
	if(vst[o]) return (isFg == fg[o]) ? 0 : INF;
	else {
		fg[o] = isFg; vst[o] = true;
		int i, gn = isFg ? 1 : -1;
		for(i = 0; i < n; i++)
			if(dlk[o][i]) gn += dfs(i, !isFg);
		return gn;
	}
}