Codeforces 1152E（欧拉路径）

看样例然后发现只要求一个一笔画即可，用板子。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
int n, b[maxn], c[maxn], _b[maxn], _c[maxn];
int d[maxn << 1], tot;
vector<pair<int, int>> adj[maxn << 1];
bool vis[maxn];
int ans[maxn];
int cnt;
void dfs(int cur) {
while (!adj[cur].empty()) {
auto tmp = adj[cur].back();
adj[cur].pop_back();
if (!vis[tmp.second]) {
vis[tmp.second] = 1;
dfs(tmp.first);
ans[cnt++] = tmp.first;
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++)
scanf("%d", &b[i]), d[++tot] = b[i];
for (int i = 1; i < n; i++)
scanf("%d", &c[i]), d[++tot] = c[i];
sort(d + 1, d + 1 + tot);
tot = unique(d + 1, d + 1 + tot) - d - 1;
for (int i = 1; i < n; i++) {
_b[i] = lower_bound(d + 1, d + 1 + tot, b[i]) - d;
_c[i] = lower_bound(d + 1, d + 1 + tot, c[i]) - d;
if (_b[i] > _c[i]) {
puts("-1");
return 0;
}
adj[_b[i]].push_back({_c[i], i});
adj[_c[i]].push_back({_b[i], i});
}
vector<int> v;
for (int i = 1; i <= tot; i++) {
if (adj[i].size() % 2 == 1)
v.push_back(i);
}
if (v.size() == 2) {
dfs(v[0]);
ans[cnt++] = v[0];
} else if(v.size() == 0) {
dfs(1);
ans[cnt++] = 1;
}
if (cnt == n)
for (int i = cnt - 1; ~i; --i)
printf("%d ", d[ans[i]]);
else
puts("-1");
return 0;
}