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

知识点

队列，拓扑排序

解题思路

拓扑排序算法的基本思想是不断移除入度为0的节点，直到所有节点都被移除或者没有入度为0的节点。在本题中，入度为0的节点表示可以直接喂养的牛。用数组graph来表示有向图中每个节点的后继节点，并使用数组indegress来记录每个节点的入度。

然后，使用队列进行拓扑排序。将所有入度为0的节点入队，并依次取出队列中的节点，将其加入结果数组result，并将与其相邻的节点的入度减一。如果减一后的入度为0，则将该节点入队。

当队列为空时，如果result数组的大小不等于牛的数量nuwCows，则说明无法喂养完所有牛，返回一个空数组。

最后，将result数组转换为整型数组feedOrder并返回。

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
        ArrayList<Integer>[] graph = new ArrayList[numCows];
        int[] indegrees = new int[numCows];

        // 初始化图和入度数组
        for (int i = 0; i < numCows; i++) {
            graph[i] = new ArrayList<>();
        }

        // 构建有向图和入度数组
        for (int[] order : feedOrders) {
            int cowA = order[0];
            int cowB = order[1];
            graph[cowB].add(cowA);
            indegrees[cowA]++;
        }

        // 使用队列进行拓扑排序
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCows; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int cow = queue.poll();
            result.add(cow);

            // 减少依赖于当前牛的入度
            for (int nextCow : graph[cow]) {
                if (--indegrees[nextCow] == 0) {
                    queue.offer(nextCow);
                }
            }
        }

        // 如果没有遍历到所有的牛，则说明无法喂养完所有牛
        if (result.size() != numCows) {
            return new int[0];
        }

        // 将结果转换为数组并返回
        int[] feedOrder = new int[numCows];
        for (int i = 0; i < numCows; i++) {
            feedOrder[i] = result.get(i);
        }

        return feedOrder;
    }
}