Permutation recovery (Codeforces 1158C)
Tags: Greedy, dfs and similar

Vasya has written some permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, so for all $$$1 \leq i \leq n$$$ it is true that $$$1 \leq p_i \leq n$$$ and all $$$p_1, p_2, \ldots, p_n$$$ are different. After that he wrote $$$n$$$ numbers $$$next_1, next_2, \ldots, next_n$$$. The number $$$next_i$$$ is equal to the minimal index $$$i < j \leq n$$$, such that $$$p_j > p_i$$$. If there is no such $$$j$$$ let's let's define as $$$next_i = n + 1$$$.In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values $$$next_i$$$ are completely lost! If for some $$$i$$$ the value $$$next_i$$$ is lost, let's say that $$$next_i = -1$$$.You are given numbers $$$next_1, next_2, \ldots, next_n$$$ (maybe some of them are equal to $$$-1$$$). Help Vasya to find such permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, that he can write it to the notebook and all numbers $$$next_i$$$, which are not equal to $$$-1$$$, will be correct. 

Input: The first line contains one integer $$$t$$$ — the number of test cases ($$$1 \leq t \leq 100\,000$$$).Next $$$2 \cdot t$$$ lines contains the description of test cases,two lines for each. The first line contains one integer $$$n$$$ — the length of the permutation, written by Vasya ($$$1 \leq n \leq 500\,000$$$). The second line contains $$$n$$$ integers $$$next_1, next_2, \ldots, next_n$$$, separated by spaces ($$$next_i = -1$$$ or $$$i < next_i \leq n + 1$$$).It is guaranteed, that the sum of $$$n$$$ in all test cases doesn't exceed $$$500\,000$$$.In hacks you can only use one test case, so $$$T = 1$$$.

Output: Print $$$T$$$ lines, in $$$i$$$-th of them answer to the $$$i$$$-th test case.If there is no such permutations $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, that Vasya could write, print the only number $$$-1$$$.In the other case print $$$n$$$ different integers $$$p_1, p_2, \ldots, p_n$$$, separated by spaces ($$$1 \leq p_i \leq n$$$). All defined values of $$$next_i$$$ which are not equal to $$$-1$$$ should be computed correctly $$$p_1, p_2, \ldots, p_n$$$ using defenition given in the statement of the problem. If there exists more than one solution you can find any of them.

Note: In the first test case for permutation $$$p = [1, 2, 3]$$$ Vasya should write $$$next = [2, 3, 4]$$$, because each number in permutation is less than next. It's easy to see, that it is the only satisfying permutation.In the third test case, any permutation can be the answer because all numbers $$$next_i$$$ are lost.In the fourth test case, there is no satisfying permutation, so the answer is $$$-1$$$.

Sample Inputs:
6
3
2 3 4
2
3 3
3
-1 -1 -1
3
3 4 -1
1
2
4
4 -1 4 5

Sample Outputs:
1 2 3
2 1
2 1 3
-1
1
3 2 1 4

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def topological_sort():
    (q, k) = ([], 0)
    cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        for u in range(s[i], s[i + 1]):
            cnt[G[u]] += 1
    for i in range(1, n + 1):
        if not cnt[i]:
            q.append(i)
    while len(q) ^ k:
        i = q[k]
        for u in range(s[i], s[i + 1]):
            j = G[u]
            cnt[j] -= 1
            if not cnt[j]:
                q.append(j)
        k += 1
    return q

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    ma[get_root(s)] = max(ma[rs], ma[rt])
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
t = int(input())
ans = []
for _ in range(t):
    n = int(input()) + 1
    nx = [0] + list(map(int, input().split()))
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    ma = [i for i in range(n + 1)]
    (x, s) = ([], [0] * (n + 3))
    for i in range(n - 1, 0, -1):
        if nx[i] == -1:
            continue
        s[i + 2] += 1
        x.append(i)
        x.append(nx[i])
        u = i + 1
        while u < nx[i]:
            s[u + 2] += 1
            x.append(u)
            x.append(i)
            unite(i, u)
            u = ma[get_root(u)] + 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    m = len(x) // 2
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    g = topological_sort()
    if len(g) ^ n:
        ans0 = [-1]
    else:
        ans0 = [0] * (n - 1)
        u = 1
        for i in g:
            if i ^ n:
                ans0[i - 1] = u
                u += 1
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    l = list(map(int, input().split()))
    stack = []
    out = [-1] * n
    curr = 0
    works = True
    for i in range(n):
        while stack and stack[-1][0] == i:
            (_, j) = stack.pop()
            curr += 1
            out[j] = curr
        nex = l[i] - 1
        if nex == -2:
            curr += 1
            out[i] = curr
        elif stack and nex > stack[-1][0]:
            works = False
        else:
            stack.append((nex, i))
    while stack:
        (_, j) = stack.pop()
        curr += 1
        out[j] = curr
    if works:
        print(*out)
    else:
        print(-1)

Solution (Python):
import sys
inp = []
inp_idx = 0

def dfs(node, adj, n):
    timer = n
    perm = [0] * (n + 1)
    perm[node] = timer
    timer -= 1
    stack = [node]
    while stack:
        node = stack[-1]
        if adj[node]:
            neighbor = adj[node].pop()
            stack.append(neighbor)
            perm[neighbor] = timer
            timer -= 1
        else:
            stack.pop()
    return perm

def check(n, nxt, perm):
    stack = [n]
    for i in range(n - 1, -1, -1):
        while stack[-1] < perm[i]:
            stack.pop()
        if stack[-1] != perm[nxt[i]]:
            return False
        stack.append(perm[i])
    return True

def solve():
    global inp
    global inp_idx
    global perm
    global timer
    n = inp[inp_idx]
    inp_idx += 1
    nxt = []
    for _ in range(n):
        nxt.append(inp[inp_idx])
        inp_idx += 1
    for i in range(n):
        nxt[i] = i + 1 if nxt[i] == -1 else nxt[i] - 1
    adj = [[] for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        adj[nxt[i]].append(i)
    perm = dfs(n, adj, n)
    print(-1) if not check(n, nxt, perm) else print(*list(map(lambda x: x + 1, perm[:-1])))
if __name__ == '__main__':
    inp = [int(x) for x in sys.stdin.read().split()]
    t = inp[0]
    inp_idx = 1
    for test in range(t):
        solve()