Selling a Menagerie (Codeforces 1872F)
Tags: Math, dsu

You are the owner of a menagerie consisting of $$$n$$$ animals numbered from $$$1$$$ to $$$n$$$. However, maintaining the menagerie is quite expensive, so you have decided to sell it!It is known that each animal is afraid of exactly one other animal. More precisely, animal $$$i$$$ is afraid of animal $$$a_i$$$ ($$$a_i \neq i$$$). Also, the cost of each animal is known, for animal $$$i$$$ it is equal to $$$c_i$$$.You will sell all your animals in some fixed order. Formally, you will need to choose some permutation$$$^\dagger$$$ $$$p_1, p_2, \ldots, p_n$$$, and sell animal $$$p_1$$$ first, then animal $$$p_2$$$, and so on, selling animal $$$p_n$$$ last.When you sell animal $$$i$$$, there are two possible outcomes: If animal $$$a_i$$$ was sold before animal $$$i$$$, you receive $$$c_i$$$ money for selling animal $$$i$$$. If animal $$$a_i$$$ was not sold before animal $$$i$$$, you receive $$$2 \cdot c_i$$$ money for selling animal $$$i$$$. (Surprisingly, animals that are currently afraid are more valuable). Your task is to choose the order of selling the animals in order to maximize the total profit. For example, if $$$a = [3, 4, 4, 1, 3]$$$, $$$c = [3, 4, 5, 6, 7]$$$, and the permutation you choose is $$$[4, 2, 5, 1, 3]$$$, then: The first animal to be sold is animal $$$4$$$. Animal $$$a_4 = 1$$$ was not sold before, so you receive $$$2 \cdot c_4 = 12$$$ money for selling it. The second animal to be sold is animal $$$2$$$. Animal $$$a_2 = 4$$$ was sold before, so you receive $$$c_2 = 4$$$ money for selling it. The third animal to be sold is animal $$$5$$$. Animal $$$a_5 = 3$$$ was not sold before, so you receive $$$2 \cdot c_5 = 14$$$ money for selling it. The fourth animal to be sold is animal $$$1$$$. Animal $$$a_1 = 3$$$ was not sold before, so you receive $$$2 \cdot c_1 = 6$$$ money for selling it. The fifth animal to be sold is animal $$$3$$$. Animal $$$a_3 = 4$$$ was sold before, so you receive $$$c_3 = 5$$$ money for selling it.Your total profit, with this choice of permutation, is $$$12 + 4 + 14 + 6 + 5 = 41$$$. Note that $$$41$$$ is not the maximum possible profit in this example.$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is present in the array).

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Then follow the descriptions of the test cases.The first line of each test case description contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of animals.The second line of the test case description contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$, $$$a_i \neq i$$$) — $$$a_i$$$ means the index of the animal that animal $$$i$$$ is afraid of.The third line of the test case description contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — the costs of the animals.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: Output $$$t$$$ lines, each containing the answer to the corresponding test case. The answer should be $$$n$$$ integers — the permutation $$$p_1, p_2, \ldots, p_n$$$, indicating in which order to sell the animals in order to maximize the profit. If there are multiple possible answers, you can output any of them.


Sample Inputs:
8
3
2 3 2
6 6 1
8
2 1 4 3 6 5 8 7
1 2 1 2 2 1 2 1
5
2 1 1 1 1
9 8 1 1 1
2
2 1
1000000000 999999999
7
2 3 2 6 4 4 3
1 2 3 4 5 6 7
5
3 4 4 1 3
3 4 5 6 7
3
2 1 1
1 2 2
4
2 1 4 1
1 1 1 1

Sample Outputs:
1 2 3
2 4 5 1 6 3 7 8
3 4 5 1 2
1 2
7 5 1 3 2 6 4
5 3 2 4 1
3 2 1
3 4 1 2

Solution (Python):
def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = [x - 1 for x in map(int, input().split())]
        c = list(map(int, input().split()))
        income = [0] * n
        for ai in a:
            income[ai] += 1
        inc0 = []
        for (i, count) in enumerate(income):
            if count == 0:
                inc0.append(i)
        ans = []
        i = 0
        while i < len(inc0):
            ans.append(inc0[i] + 1)
            income[a[inc0[i]]] -= 1
            if income[a[inc0[i]]] == 0:
                inc0.append(a[inc0[i]])
            i += 1
        for i in range(len(income)):
            if income[i] == 0:
                continue
            cycle = [(c[i], i)]
            ai = a[i]
            while ai != i:
                cycle.append((c[ai], ai))
                ai = a[ai]
            (min_i, min_c) = (0, cycle[0][0])
            for j in range(1, len(cycle)):
                if min_c > cycle[j][0]:
                    (min_i, min_c) = (j, cycle[j][0])
            for j in list(range(min_i + 1, len(cycle))) + list(range(min_i + 1)):
                ans.append(cycle[j][1] + 1)
                income[cycle[j][1]] -= 1
        print(' '.join(map(str, ans)))
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = [-1] + [int(x) for x in input().split()]
    c = [-1] + [int(x) for x in input().split()]
    used = [False] * (n + 1)
    count_in = [0] * (n + 1)
    for ai in a[1:]:
        count_in[ai] += 1
    ans = []

    def dfs(x):
        assert not count_in[x]
        assert not used[x]
        ans.append(x)
        used[x] = True
        count_in[a[x]] -= 1
        if not count_in[a[x]]:
            dfs(a[x])
    for i in range(1, n + 1):
        if not used[i] and (not count_in[i]):
            dfs(i)
    for i in range(1, n + 1):
        if used[i]:
            continue
        assert count_in[i] == 1, (ans, i, count_in[i])
        cyc = []
        pos = i
        while True:
            cyc.append(pos)
            used[pos] = True
            pos = a[pos]
            if pos == i:
                break
        mindex = min(range(len(cyc)), key=lambda i: c[cyc[i]])
        for j in range(len(cyc)):
            ans.append(cyc[(mindex + 1 + j) % len(cyc)])
    print(' '.join(map(str, ans)))

Solution (Python):
N = int(input())
for j in range(N):
    n = int(input())
    a = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]
    seen = set()
    o = []
    i = 0
    while i < n:
        if i not in seen:
            if a[i] in seen:
                seen.add(i)
                o.append(i)
            else:
                lc = []
                sc = set()
                ci = i
                while ci not in seen:
                    lc.append(ci)
                    sc.add(ci)
                    seen.add(ci)
                    ci = a[ci]
                if ci in sc:
                    min_c = c[lc[-1]]
                    cci = -1
                    min_i = cci
                    while lc[cci] != ci:
                        if c[lc[cci]] < min_c:
                            min_c = c[lc[cci]]
                            min_i = cci
                        cci -= 1
                    if c[lc[cci]] < min_c:
                        min_c = c[lc[cci]]
                        min_i = cci
                    if min_i != -1:
                        llc = lc[:cci] + lc[min_i + 1:] + lc[cci:min_i + 1]
                        lc = llc
                for ii in range(len(lc)):
                    o.append(lc[-ii - 1])
        i += 1
    print(' '.join([str(o[-i - 1] + 1) for i in range(n)]))