codeforcesRound#259(div2)E解题报告

#include 
#include 
#define N_max 123456

using namespace std;

int n, m, fa[N_max], want[N_max];
int Odd_n, Odd_x, haveOdd[N_max];
vector  G[N_max], ans;

int getf(int x) {
	return (fa[x] == x) ? x : fa[x] = getf(fa[x]);
}
void addedge(int x, int y) {
	G[x].push_back(y);
}

void init() {
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {
	int x, y;

	scanf("%d%d", &x, &y);

	int tmpx=getf(x);
	int tmpy=getf(y);
	if (tmpx != tmpy) {
	fa[tmpx] = tmpy;
	addedge(x, y);
	addedge(y, x);
	}
	}

	for (int i = 1; i <= n; i++) {
	scanf("%d", &want[i]);

	if (want[i]) haveOdd[getf(i)] = 1;
	}

	for (int i = 1; i <= n; i++)
	if (haveOdd[i]) {
	Odd_n++;
	Odd_x = i;
	}
}

void dfs(int now, int pre) {
	ans.push_back(now);
	want[now] ^= 1;

	for (int i = 0; i < G[now].size(); i++) {
	int nex = G[now][i];
	if (nex == pre) continue;

	dfs(nex, now);
	ans.push_back(now);
	want[now] ^= 1;

	if (want[nex]) {
	ans.push_back(nex);
	want[nex] ^= 1;
	ans.push_back(now);
	want[now] ^= 1;
	}
	}
}

void solve() {
	if (Odd_n == 0) {
	printf("0\n");
	return;
	}

	if (Odd_n > 1) {
	printf("-1\n");
	return;
	}

	dfs(Odd_x, -1);
	int x = 0;
	if (want[Odd_x]) x=1;

	printf("%d\n", ans.size() - x);
	for (int i = x; i < ans.size(); i++)
	printf("%d ", ans[i]);
}

int main() {
	init();
	solve();
}