题解 | 谍中谍中谍中谍中谍...

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = in.nextInt() - 1;
        }

        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) {
            indeg[p[i]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            topoOrder.add(u);
            int v = p[u];
            indeg[v]--;
            if (indeg[v] == 0) {
                queue.offer(v);
            }
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (indeg[i] > 0) {
                ans[i] = i;
            }
        }

        // p[u]是拓扑排序靠后的 一定被计算过
        for (int i = topoOrder.size() - 1; i >= 0; i--) {
            int u = topoOrder.get(i);
            ans[u] = ans[p[u]];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(ans[i] + 1).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

就是找到每个点到环的入口。

巧妙使用拓扑排序进行DP。