Codeforces 1159E 拓扑排序

题意及思路：https://www.cnblogs.com/dd-bond/p/10859864.html

代码：

#include <bits/stdc++.h>
#define LL long long
#define db double
using namespace std;
const int maxn = 500010;
stack<pair<int ,int> >s;
vector<int> G[maxn];
int a[maxn], ans[maxn], tot, n;
void topsort(void) {
queue<int> q;
q.push(n + 1);
while(!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < G[x].size(); i++) {
int y = G[x][i];
ans[y] = tot--;
q.push(y);
}
}
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
tot = n;
while(!s.empty())s.pop();
for (int i = 1; i <= n + 1; i++) G[i].clear();
bool flag = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if(a[i] == -1) a[i] = i + 1;
while(!s.empty() && s.top().second <= i) s.pop();
if(!s.empty() && a[i] > s.top().second) {
flag = 1;
} else {
s.push(make_pair(i, a[i]));
G[a[i]].push_back(i);
}
}
if(flag) {
printf("-1n");
}
else {
topsort();
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
printf("n");
}
}
}