题目链接：点击查看

题目大意：第一行给出两个数n和m，n代表有n个数，m代表有m组比较关系，接着给出m组关系pos_a和pos_b，代表在一个数组中，pos_a和pos_b存在一种比较关系

现在要求我们构造出两个数组，要求是：

1. 第一个数组是1~n的一种全排列
2. 第二个数组只有两个数字是重复的，其余的数字从1~n中取值
3. 第一个数组和第二个数组的比较关系必须保持一致

题目分析：这个题目的第三点要求比较难看懂，举个例子吧，我们现在的给出两组关系，1 2和2 3，现在构造出的数组1是：1 3 2，那么第一个数和第二个数的关系是pos_1<pos_2，第二个数和第三个数的关系是pos_2>pos_3，我们接下来需要构造的数组需要满足除了上面的第二个条件之外，还需要满足pos_1<pos_2以及pos_2>pos_3，所以我们可以随意构造出满足条件的一种，比如1 3 1，那么现在大概应该能摸清楚这个题目的大体意思了，接下来该想一下怎么构造通项，也就是可以满足所有式子的一种构造方法，我们首先想一下答案为NO的情况，也就是无法构造的情况，因为现在有n个数，若两两之间产生关系的话，最多有n*(n-1)种关系，又因为这个题目提前说明了没两个位置的关系至多给一次，所以可以当做有向边来处理，也就是最多会有n*(n-1)/2种关系就可以确定唯一的一个数组了，所以当m大于等于n*(n-1)/2的时候是无解的，现在我们继续讨论有解的情况，如果题目给出的对应关系m小于等于n*(n-1)/2的话，那么必定至少可以找出一组的两个位置没有对应关系，那么我们在这两个位置上进行操作就好了，对于数组1，我们在这两个位置上放上最大值和次大值，或者最小值或次小值，然后在第二个数组上都放上最大值或最小值或次大值或次小值都可以，只要对应起来就可以了，这样其余有关系的位置上，两个数组的值都一模一样了，对应关系也肯定都满足，这样构造出来的答案就可以满足通项了

对于这个题目，我是选择用最大值和次大值来构造的，具体实现来看代码吧

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;

const int N=1e5+100;

int n,m;

pair<int,int>a[N];

pair<int,int>find()
{
	int cnt=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(make_pair(i,j)!=a[++cnt])
			{
				return make_pair(i,j);
			}
}

int main()
{
//  freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int num1,num2;
		scanf("%d%d",&num1,&num2);
		a[i]=make_pair(min(num1,num2),max(num1,num2));//保存所有的对应关系，让较小的下标在前面
	}
	if(m>=n*(n-1)/2)//特判
		return 0*printf("NO\n");
	printf("YES\n");
	sort(a+1,a+1+m);//对于所有关系排序
	pair<int,int>pos=find();//随便找一个没有对应关系的两个位置
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(i==pos.first)//在某个位置上放最大值
			printf("%d ",n);
		else if(i==pos.second)//另一个位置上放次大值
			printf("%d ",n-1);
		else
			printf("%d ",++cnt);
	}
	printf("\n");
	cnt=1;
	for(int i=1;i<=n;i++)
	{
		if(i==pos.first)//都放上最大值或次大值
			printf("%d ",n);
		else if(i==pos.second)//同上
			printf("%d ",n);
		else
			printf("%d ",++cnt);
	}
	
	
   	
   	
   	
   	
     
     
     
     
     
     
     
    return 0;
}

代码：