题目链接：codeforces1152E
题意
有长为(n)的数组(a)和排列(p)，构造以下数组：
-
长为(n-1)的数组(b)，(b_i = min{a_i, a_{i+1}})
-
长为(n-1)的数组(c)，(c_i = max{a_i, a_{i+1}})
-
长为(n-1)的数组(b')，(b_i' = b_{p_i})
-
长为(n-1)的数组(c')，(c_i' = c_{p_i})
现给定({b'})和({c'})，输出一组可能的原数组(a)，无解输出(-1)。
数据范围：(n≤1e5)
题解
大概手膜一下就知道，原题相当于把每个(b_i)和(c_i)之间连一条边求欧拉路径（或回路）
然而并不会这个东西去学习了一下。
Hierholzer算法可以在(O(V+E))的时间复杂度内求解欧拉路径。
首先判定是否有解并找好起点。
然后我们在图中随机游走。有时候我们会走进一个死胡同。
但是如果我们删掉已经走过的边，剩下的图是存在欧拉回路的，而且这张图的点集和已经走过部分的点集一定是有交的。
那么我们在走到这个交点时，先不走这条路径，而是把图剩下部分先求个欧拉回路后回到这个点，然后再走完剩下的路径。
具体实现时就是在图中随机游走，直到离开一个点的时候把这个点入栈，随后从栈底到栈顶输出即可。
但是需要注意两个细节。
一个是不要忘记判断图是否联通。
其次是在(dfs)时需要加上当前弧优化，不然会被(1-2, 1-2, 1-2, 1-2 ...) 这样的数据卡到(O(E^2))
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, E = 1, tot;
int a[N], b[N], num[N];
int fir[N], nex[N], arr[N], deg[N], ans[N], used[N];
stack<int> st;
void Add_Edge(int x, int y) {
nex[++E] = fir[x];
fir[x] = E; arr[E] = y;
}
void dfs(int x) {
for (int &i = fir[x]; i; i = nex[i]) {
if (used[i]) continue;
used[i] = used[i ^ 1] = 1;
dfs(arr[i]);
}
st.push(x);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
scanf("%d", &a[i]);
num[++tot] = a[i];
}
for (int i = 1; i < n; ++i) {
scanf("%d", &b[i]);
num[++tot] = b[i];
}
sort(num + 1, num + tot + 1);
tot = unique(num + 1, num + tot + 1) - num - 1;
for (int i = 1; i < n; ++i) {
a[i] = lower_bound(num + 1, num + tot + 1, a[i]) - num;
b[i] = lower_bound(num + 1, num + tot + 1, b[i]) - num;
if (a[i] > b[i]) return 0 * puts("-1");
Add_Edge(a[i], b[i]);
Add_Edge(b[i], a[i]);
++deg[a[i]]; ++deg[b[i]];
}
int u = 0, v = 0;
for (int i = 1; i <= tot; ++i) {
if (deg[i] % 2 == 0) continue;
if (!u) u = i;
else if (!v) v = i;
else return 0 * puts("-1");
}
if (!u) u = 1;
dfs(u);
int len = 0;
if (st.size() != n) return 0 * puts("-1");
while (!st.empty()) ans[++len] = st.top(), st.pop();
for (int i = 1; i <= len; ++i) {
printf("%d ", num[ans[i]]);
}
puts("");
return 0;
}