拓扑排序：DAG 上的线性化

public int[] topologicalSort(int n, int[][] edges) {
    List<Integer>[] graph = new ArrayList[n];
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();

    for (int[] e : edges) {
        graph[e[0]].add(e[1]);
        inDegree[e[1]]++;
    }

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

    int[] order = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;
        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) queue.offer(v);
        }
    }

    // idx < n 说明有环
    return idx == n ? order : new int[0];
}

public int[] topologicalSortDFS(int n, int[][] edges) {
    List<Integer>[] graph = new ArrayList[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int[] e : edges) graph[e[0]].add(e[1]);

    int[] state = new int[n];   // 0=未访问, 1=访问中, 2=已完成
    Deque<Integer> stack = new ArrayDeque<>();
    boolean[] hasCycle = {false};

    for (int i = 0; i < n; i++) {
        if (state[i] == 0) {
            dfs(graph, i, state, stack, hasCycle);
        }
    }
    if (hasCycle[0]) return new int[0];

    int[] order = new int[n];
    for (int i = 0; i < n; i++) order[i] = stack.pop();
    return order;
}

private void dfs(List<Integer>[] graph, int u, int[] state,
                 Deque<Integer> stack, boolean[] hasCycle) {
    state[u] = 1;
    for (int v : graph[u]) {
        if (state[v] == 1) { hasCycle[0] = true; return; }
        if (state[v] == 0) dfs(graph, v, state, stack, hasCycle);
    }
    state[u] = 2;
    stack.push(u);
}

public boolean canFinish(int numCourses, int[][] prerequisites) {
    return topologicalSort(numCourses, prerequisites).length == numCourses;
}

public int longestPath(int n, int[][] edges, int[] weight) {
    List<int[]>[] graph = new ArrayList[n];
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int[] e : edges) {
        graph[e[0]].add(new int[]{e[1], e[2]});
        inDegree[e[1]]++;
    }

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

    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            dist[v] = Math.max(dist[v], dist[u] + w);
            if (--inDegree[v] == 0) queue.offer(v);
        }
    }
    return Arrays.stream(dist).max().getAsInt();
}