题解 | #牛群的喂养顺序II# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numCows int整型
     * @param feedOrders int整型二维数组
     * @return int整型一维数组
     */
    public int[] findFeedOrderII (int numCows, int[][] feedOrders) {
        // write code here
        int[] indegree = new int[numCows];
        List<List<Integer>> adjacency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < numCows; ++i) {
            adjacency.add(new ArrayList<>());
        }

        for (int[] order : feedOrders) {
            int from = order[1], to = order[0];
            indegree[to]++;
            adjacency.get(from).add(to);
        }

        for (int i = 0; i < numCows; ++i) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            result.add(cur);

            for (int next : adjacency.get(cur)) {
                if (--indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        if (result.size() == numCows) {
            int[] res = new int[result.size()];
            for (int i = 0; i < result.size(); i++) {
                res[i] = result.get(i);
            }
            return res;
        } else {
            return new int[0];
        }
    }
}

编程语言是Java。

该题考察的知识点包括：

• 图的拓扑排序
• 邻接表的表示和操作
• 队列的使用

代码的文字解释如下：

1. 创建整型数组 indegree，用于记录每头牛的入度。
2. 整型二维列表 adjacency，用于表示牛之间的邻接关系。
3. 队列 queue 和整型列表 result，用于存储拓扑排序的结果。
4. 初始化邻接表 adjacency，将牛数量对应的空列表添加到其中。
5. 遍历二维整数数组 feedOrders：根据饲料顺序中的信息，将被喂食牛的入度加一，并将其添加到相应的邻接表中。
6. 遍历入度数组 indegree：将入度为零的牛添加到队列中。
7. 进行广度优先搜索（BFS）的拓扑排序：在每次循环中，取出队列的第一个牛 cur。将 cur 添加到结果列表 result 中。遍历 cur 的邻接表中的每个奶牛 next：将 next 的入度减一。如果 next 的入度为零，将其加入队列中。
8. 检查结果列表的长度是否等于牛数量：如果相等，将结果列表转换为数组并返回。否则，返回空数组。