题解 | #体育课测验(二)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numProject int整型
     * @param groups int整型ArrayList<ArrayList<>>
     * @return int整型ArrayList
     */
    public static ArrayList<Integer> findOrder(int numProject, ArrayList<ArrayList<Integer>> groups) {
        /**
		拓扑排序是一种基于有向无环图（DAG）的排序算法，它可以将DAG中的节点按照一定的顺序进行排序。在这个问题中，每个项目可以看作是DAG中的一个节点，每个先后顺序规定可以看作是DAG中的一条有向边。我们可以使用拓扑排序来确定每个项目的执行顺序。
		**/
        // 构建邻接表和入度数组
        ArrayList<Integer>[] adj = new ArrayList[numProject];
        int[] indegree = new int[numProject];
        for (int i = 0; i < numProject; i++) {
            adj[i] = new ArrayList<>();
        }
        for (ArrayList<Integer> group : groups) {
            int first = group.get(0);
            int second = group.get(1);
            adj[second].add(first);
            indegree[first]++; // 被越多节点要求后置的节点入度越高,每一个入度相当于加上了一层封印
        }

        // 将入度为0的节点加入队列中
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numProject; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        // 拓扑排序
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int successor : adj[node]) {
                indegree[successor]--; // 一个节点被放入后,其邻接表里的所有数入度解封一层
                if (indegree[successor] == 0) { // 全部解封后可以进队排列进结果
                    queue.offer(successor);
                }
            }
        }

        // 检查是否存在环-如果存在环,两个节点互锁,会导致两个数都不会被放入queue,一直封印
        if (result.size() != numProject) { // queue都poll空了, 还没都输出, 就有环
            return new ArrayList<>();
        }

        return result;
    }
}