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

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）。