2020小米网络赛第一场 G Tree Projection（拓扑序，构造）

本文主要是介绍2020小米网络赛第一场 G Tree Projection（拓扑序，构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
构造一棵树，使得按照$A1$为根拓扑排序可以得到$A$序列，按照$B1$为根拓扑排序可以得到$B$序列。

思路：
表示很巧妙，没想出来，直接搬题解吧

这道题倒是纠正了我一直以来的误区，我以前一直用bfs写拓扑，所以转换到树上的时候想当然的把bfs序与拓扑序等价了起来。但其实拓扑排序也可以是树上dfs序，只要满足前驱限制条件的序列都是拓扑序。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 2e5 + 7;
int a[maxn],b[maxn];
int posA[maxn]; //i在a数组中的位置int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);posA[a[i]] = i;}for(int i = 1;i <= n;i++) {scanf("%d",&b[i]);}printf("YES\n");int cur = b[1];for(int i = 2;i <= n;i++) {printf("%d %d\n",cur,b[i]);if(posA[cur] > posA[b[i]]) {cur = b[i];}}return 0;
}

这篇关于2020小米网络赛第一场 G Tree Projection（拓扑序，构造）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---