模拟赛的时候这道题细节写挂了，硬是调不出来。。。
首先想到拓补排序。然后可以发现，正反各跑一次可以获得每个点的取值范围，即上界和下界。（特殊地，对于已知点，其上下界相等且等于自己）
然后，将这些上下界看成一条条线段，问题转化：\(n\) 个线段区间，每次取 \([1,n]\) 中一个值，且包含在线段内。
经典问题。按照 \(r\) 排序，将排列存在 \(set\) 中， 最后对左端点 \(lowerbound\) 一下即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
int n;
int a[N];
set <int> s;
struct node{
int u, v, next;
} ;
namespace zheng{
node t[N << 1];
int head[N];
int bian = 0;
inline void addedge(int u, int v){
t[++bian] = (node){u, v, head[u]}, head[u] = bian;
return ;
}
int in[N];
}
namespace fan{
node t[N << 1];
int head[N];
int bian = 0;
inline void addedge(int u, int v){
t[++bian] = (node){u, v, head[u]}, head[u] = bian;
return ;
}
int in[N];
}
int lim[N], lmax[N];
struct point{
int l, r, id;
bool operator < (const point& a) const{
return r < a.r || (r == a.r && l < a.l);
}
} h[N] ;
bool isfixed(int i){
return a[i] >= 1 && a[i] <= n;
}
void topo_fan(){
queue <int> q;
for(int i = 1; i <= n; i++){
if(isfixed(i)) lim[i] = a[i];
else lim[i] = 1;
}
for(int i = 1; i <= n; i++){
if(!fan::in[i]) q.push(i);
}
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = fan::head[u]; i; i = fan::t[i].next){
int v = fan::t[i].v;
lim[v] = max(lim[v], lim[u] + 1);
fan::in[v]--;
if(!fan::in[v]){
q.push(v);
}
}
}
return ;
}
int ans[N];
void topo_zheng(){
queue <int> q;
for(int i = 1; i <= n; i++){
lmax[i] = n;
if(isfixed(i)) lmax[i] = a[i];
}
for(int i = 1; i <= n; i++)
if(!zheng::in[i]) q.push(i);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = zheng::head[u]; i; i = zheng::t[i].next){
int v = zheng::t[i].v;
lmax[v] = min(lmax[v], lmax[u] - 1);
zheng::in[v]--;
if(zheng::in[v] == 0) q.push(v);
}
}
return ;
}
int m;
void clean(){
for(int i = 0; i <= n; i++) zheng::head[i] = fan::head[i] = 0;
zheng::bian = fan::bian = 0;
for(int i = 0; i <= n; i++)
zheng::in[i] = fan::in[i] = 0;
for(int i = 0; i <= n; i++)
h[i].l = h[i].r = 0;
s.clear();
return ;
}
int main(){
// freopen("hh.txt", "r", stdin);
int T; cin >> T;
while(T--){
clean();
cin >> n >> m;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++){
s.insert(i);
ans[i] = 0;
}
for(int i = 1; i <= m; i++){
int x, y;
scanf("%d %d", &x, &y);
zheng::addedge(y, x);
zheng::in[x]++;
fan::addedge(x, y);
fan::in[y]++;
}
topo_fan(); //
topo_zheng();
for(int i = 1; i <= n; i++){
h[i].l = lim[i];
h[i].r = lmax[i];
h[i].id = i;
}
sort(h + 1, h + n + 1);
bool flag = 1;
for(int i = 1; i <= n; i++){
set<int>::iterator it = s.lower_bound(h[i].l);
if(*it > h[i].r || it == s.end()){
flag = 0;
break;
}
ans[h[i].id] = *it;
s.erase(it);
}
if(!flag){
puts("-1");
continue;
}
for(int i = 1; i <= n; i++)
printf("%d ", ans[i]);
cout << endl;
//
}
return 0;
}