2020ICPC·小米 网络选拔赛第一场 G-Tree Projection (构造)
题面：
题意：
给定一个整数\(\mathit n\) 以及两个\(1\dots n\) 的全排列\(A,B\)。
请构造一个\(\mathit n\)个节点的无根树，使其以\(A_1\) 为根时，全排列\(\mathit A\) 是其一个合法的拓扑序。
使其以\(B_1\) 为根时，全排列\(\mathit B\) 是其一个合法的dfs序。
输出：
辅助数组：\(pos_i\) 代表第\(\mathit i\)个数在排列\(\mathit A\) 中的位置。
枚举\(i\in[2,n]\)，
开一个辅助变量\(now\) 代表 \(B_1,\dots ,B_{i-1}\)中拓扑序较小(在排列\(\mathit A\) 中的位置更靠前)的数。
连边\((B[i],now)\)，然后如果\(pos_{B_i}<pos_{now}\) 就更新now。
这样生成的树就满足条件。
证明：
代码：
int n;
int a[maxn];
int b[maxn];
int posa[maxn];
int main()
{
#if DEBUG_Switch
freopen("D:\\code\\input.txt", "r", stdin);
#endif
//freopen("D:\\code\\output.txt","w",stdout);
n = readint();
repd(i, 1, n) {
a[i] = readint();
posa[a[i]] = i;
}
repd(i, 1, n) {
b[i] = readint();
}
int now = b[1];
printf("YES\n");
repd(i, 2, n) {
printf("%d %d\n", now, b[i] );
if (posa[b[i]] < posa[now]) {
now = b[i];
}
}
return 0;
}