题解 | #牛群的喂养顺序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
        // 拓扑排序
        List<List<Integer>> g = new ArrayList<>();
        int[] d = new int[numCows];
        for (int i = 0; i < numCows; i++) {
            g.add(new ArrayList<>());
        }
        for (int[] v : feedOrders) {
            int a = v[0], b = v[1];
            g.get(b).add(a);
            d[a]++;
        }

// bfs
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCows; i++) {
            if (d[i] == 0) {
                q.add(i);
            }
        }

        List<Integer> res = new ArrayList<>();
        while (!q.isEmpty()) {
            int t = q.poll();
            res.add(t);
            for (int x : g.get(t)) {
                if (--d[x] == 0) {
                    q.add(x);
                }
            }
        }

        if (res.size() == numCows) {
            return res.stream().mapToInt(Integer::intValue).toArray();
        } else {
            return new int[0];
        }
    }
}

代码使用的编程语言是Java。

该题考察的知识点是拓扑排序和有向无环图（DAG）。

代码的文字解释如下：

该函数接受输入参数numCows表示奶牛的数量，feedOrders是一个二维数组，表示喂食订单。

构建一个有向图g和一个入度数组d。对于每个喂食订单[v[0], v[1]]，将v[1]作为起点，v[0]作为终点，表示v[1]依赖于v[0]，也就是v[0]需要在v[1]之前被喂食。同时，增加v[0]的入度，即d[v[0]]++。

使用拓扑排序算法来确定喂食的顺序。创建一个队列q，并将所有入度为0的奶牛放入队列中。

在每一轮的循环中，取出队列的首元素t，并将其添加到结果列表res中。然后，遍历从t出发的所有边，即g[t]，对于每条边(x, t)，将x的入度减1。如果减1后的入度变为0，说明x没有其他依赖，可以被喂食，将x加入队列q中。

当队列q为空时，如果结果列表res的长度等于奶牛的数量numCows，说明所有的喂食订单都可以被满足，将res转换为int数组并返回。否则，表示存在环路或有未满足的喂食订单，返回空数组。