TreeProjection

NC211818. TreeProjection

描述

Given two $1\sim n$ permutations $A, B_{}$ , you should construct an unrooted tree $T_{}$ , which satisfies that $A_{}$ is a possible topological order of $T_{}$ if $A_1$ is made the root, and that $B_{}$ is a possible dfs order of $T_{}$ if $B_1$ is made the root.

Here, a permutation $P_{}$ of size $n_{}$ is a valid topological order of a rooted tree $T_{}$ of size $n_{}$ iff that for all edges in $T_{}$ , the parent nodes are at front of the child nodes in permutation $P_{}$ .

输入描述

The first line contains one integer , denoting the size of permutations.

The second line contains  integers , denoting permutation .

The third line contains  integers , denoting permutation .

输出描述

If solution exists, print "YES" in one line, and following  lines each contains two integers , denoting one edge in . If multiple solutions exist, print any one of them. If no solution, print "NO" in one line.

示例1

输入:

5
2 1 4 3 5
4 2 5 1 3

输出:

说明:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 477ms, 内存消耗: 5364K, 提交时间: 2020-10-25 16:45:59

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n;
int a[N],b[N],p[N];

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		p[a[i]]=i;
	}
	for(int i=1;i<=n;++i)cin>>b[i];
	int x=b[1];
	puts("YES");
	for(int i=2;i<=n;++i){
		cout<<b[i]<<" "<<x<<endl;
		if(p[b[i]]<p[x])x=b[i];
	}
}

上一题

下一题

详情