UOJ117 欧拉回路

现在才会求欧拉回路是不是完了。

我感觉是完了。

这个东西网上资料很多的样子，我觉得自己的表达能力存在缺陷，这里就不献丑了。

上一份代码吧。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int getc() {
	static const int L = 1 << 15;
	static char buf[L], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, L, stdin);
		if (S == T)
			return EOF;
	}
	return *S++;
}

int getint() {
	int c;
	while (!isdigit(c = getc()));
	int x = c - '0';
	while (isdigit(c = getc()))
		x = (x << 1) + (x << 3) + c - '0';
	return x;
}

#define N 100010
#define M 200010
int head[N], nxt[M << 1], pre[M << 1], from[M << 1], to[M << 1], ind;
vector<int> self[N];
bool isself[M];

void insert(int x, int y, int label) {
	from[label] = x;
	to[label] = y;
	pre[head[x]] = label;
	nxt[label] = head[x];
	head[x] = label;
}

void cutdown(int label) {
	if (label == head[from[label]]) {
		head[from[label]] = nxt[label];
		pre[head[from[label]]] = 0;
	}
	else {
		pre[nxt[label]] = pre[label];
		nxt[pre[label]] = nxt[label];
	}
}

int ans[M], id;

int deg[N];
void dfs1(int x, int laste) {
	int j;
	while (head[x] != 0) {
		j = head[x];
		cutdown(j);
		cutdown(j ^ 1);
		dfs1(to[j], j);
	}
	
	for (int i = 0; i < self[x].size(); ++i)
		ans[++id] = self[x][i];
	self[x].clear();
	if (laste != -1)
		ans[++id] = laste;
}

void solve1() {
	int n = getint(), m = getint(), i, j, a, b;
	for (i = 1; i <= m; ++i) {
		a = getint();
		b = getint();
		if (a == b) {
			self[a].push_back(i << 1);
			isself[i] = 1;
		}
		else {
			++deg[a];
			++deg[b];
			insert(a, b, i << 1);
			insert(b, a, i << 1 ^ 1);
		}
	}
	bool ok = 1;
	for (i = 1; i <= n; ++i)
		if (deg[i] % 2 == 1) {
			ok = 0;
			break;
		}
	if (!ok)
		puts("NO");
	else {
		for (i = 1; i <= n; ++i)
			if (head[i] != 0 || self[i].size() > 0) {
				dfs1(i, -1);
				break;
			}
		if (id == m) {
			puts("YES");
			for (i = id; i >= 1; --i) {
				if (isself[ans[i] >> 1])
					printf("%d ", ans[i] >> 1);
				else
					printf("%d ", (ans[i] & 1 ? -1 : 1) * (ans[i] >> 1));
			}
		}
		else
			puts("NO");
	}
}

int in[N], out[N];
void dfs2(int x, int laste) {
	int j;
	while (head[x] != 0) {
		j = head[x];
		cutdown(j);
		dfs2(to[j], j);
	}
	
	for (int i = 0; i < self[x].size(); ++i)
		ans[++id] = self[x][i];
	self[x].clear();
	if (laste != -1)
		ans[++id] = laste;
}

void solve2() {
	int n = getint(), m = getint(), i, j, a, b;
	for (i = 1; i <= m; ++i) {
		a = getint();
		b = getint();
		if (a == b)
			self[a].push_back(i);
		else {
			++out[a];
			++in[b];
			insert(a, b, i);
		}
	}
	bool ok = 1;
	for (i = 1; i <= n; ++i)
		if (in[i] != out[i]) {
			ok = 0;
			break;
		}
	if (!ok)
		puts("NO");
	else {
		for (i = 1; i <= n; ++i)
			if (head[i] > 0 || self[i].size() > 0) {
				dfs2(i, -1);
				break;
			}
		if (id == m) {
			puts("YES");
			for (i = id; i >= 1; --i)
				printf("%d ", ans[i]);
		}
		else
			puts("NO");
	}
}
int main() {
	//freopen("tt.in", "r", stdin);
	int t = getint();
	if (t == 1)
		solve1();
	else
		solve2();
	
	return 0;
}