记录编号	556366	评测结果	AAAAAAWW
题目名称	骑马修栅栏	最终得分	75
用户昵称	fsdh	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-10-19 23:29:13	内存使用	0.00 MiB

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 500 + 10;
const int MAXM = 1024 + 10;
struct node {
	int next ,to ,vis;
	node () {
		vis = 0;
	}
}edge[MAXN << 1];
int head[MAXN] ,cnt = 1;
void add (int from ,int to) {
	edge[++ cnt].next = head[from];
	head[from] = cnt;
	edge[cnt].to = to;
}
int m ,in[MAXM] ,n = -1 ,beg = -1 ,en = -1;
void bfs (int st ,int en) {
	queue <int > s;
	s.push(st);
	while (! s.empty()) {
		int u = s.front();
		s.pop();
		printf ("%d\n",u);
		int ind = 1e9 + 1 ,x;
		for (int q = head[u];~ q;q = edge[q].next) {
			if (edge[q].vis) continue;
			int v = edge[q].to;
			if (ind > v)
				ind = v ,x = q;
		}
		if (ind < 1e9) {
			edge[x].vis = edge[x ^ 1].vis = 1;
			s.push(ind);
		}
	}
}
int main () {
	memset (head ,-1 ,sizeof (head));
	memset (in ,0 ,sizeof (in));
	freopen ("fenceus.in","r",stdin);
	freopen ("fenceus.out","w",stdout);
	scanf ("%d",&m);
	int from_ ,to_;
	for (int q = 1;q <= m;++ q) {
		scanf ("%d%d",&from_ ,&to_);
		add (from_ ,to_) ,add (to_ ,from_);
		in[from_] ++ ,in[to_] ++;
		n = max (n ,max (from_ ,to_));
	}
	for (int q = 1;q <= n;++ q) {
		if (in[q] & 1) {
			if (beg == -1) beg = q;
			else en = q;
		}
	}
	if (beg == -1) bfs (1 ,n);
	else {
		if (beg > en) swap (beg ,en);
		bfs (beg ,en);
	}
	return 0;
}