体育课测验(二)

  public ArrayList<Integer> findOrder(int numProject, ArrayList<ArrayList<Integer>> groups) {
        // 使用邻接表表示图
        ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numProject; i++) {
            adjList.add(new ArrayList<>());
        }

        // 入度数组
        int[] indegree = new int[numProject];

        // 构建图
        for (ArrayList<Integer> group : groups) {
            int first = group.get(0);
            int second = group.get(1);
            adjList.get(second).add(first);
            indegree[first]++;
        }

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

        // 结果列表，用于存储项目的完成顺序
        ArrayList<Integer> result = new ArrayList<>();

        // 处理队列
        /**
         *      公共节点的每个前驱节点度为1，在最后一个前驱节点处理完成时，
         *      公共节点的度降为0，继续处理公共节点的后继节点，公共节点的后继节点度为1，
         *      确保减1操作后度降为0，能正确加入队列，继续处理
         */
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            for (int neighbor : adjList.get(current)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return result.size() == numProject ? result :  new ArrayList<>(); // 如果存在循环或未处理所有节点，则返回空列表
    }