题解 | #牛群的喂养顺序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]++;
        }
        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];
        }
    }
}

本题知识点分析：

拓扑排序；

本题解题思路分析：

1. 创建一个空的结果列表res和一个辅助变量visited，用于记录已经处理过的元素数量。
2. 对feedOrders进行遍历，统计每个元素的入度，并将入度为0的元素加入结果列表中。
3. 使用广度优先搜索的算法来处理剩下的元素。我们可以用一个队列queue来存储元素，并进行迭代处理。
4. 在迭代的过程中，我们首先从队列中取出一个元素index，然后遍历feedOrders，找到所有以index作为前驱的元素，并将它们的入度减1。如果某个元素的入度减为0，则将其加入队列和结果列表，并将visited加1。
5. 最后，我们判断visited是否等于feedOrders的长度，如果是，则返回结果列表res，否则返回一个空列表

本题使用编程语言: Java