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

知识点：拓扑排序

思路：和上一题一样，上一题其实我已经写出来了输出队列，这时返回即可

编程语言：java

如果我的思路启发了你，给个小小关注吧~

我是废江，一个从java跑到内核再准备润回java的打工人，我会持续分享从linux内核到上层java微服务等干货

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numCows int整型
     * @param feedOrders int整型二维数组
     * @return int整型一维数组
     */
    List<Integer> topLogicalSort(int[][] graph, int[] inDegree, int n) {
        List<Integer> ans = new ArrayList<>();//保存结果
        Queue<Integer> queue = new ArrayDeque<>();

        //将所有度为0的入队列
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0)
                queue.add(i);
        }

        while (!queue.isEmpty()) {
            //取队列中的元素
            int data = queue.poll();
            //存入结果之中
            ans.add(data);
            //判断这个元素的边，如果有都入队
            for (int i = 0; i < n; i++) {
                if (graph[data][i] == 1) {
                    //该节点因为被入队了，入度-1
                    inDegree[i] --;
                    //这里需要将入度=0的节点入队列，和bfs中的标记数组一个道理
                    if (inDegree[i] == 0)
                        queue.add(i);
                }
            }
        }
        return ans;
    }
    public int[] findFeedOrderII (int numCows, int[][] feedOrders) {
        // write code here
        //建图，统计入度
        int[][] graph = new int[numCows][numCows];
        int[] inDegree = new int[numCows];
        for (int i = 0; i < feedOrders.length; i++) {
            int a = feedOrders[i][0];
            int b = feedOrders[i][1];
            graph[a][b] = 1;//a到b有边
            inDegree[b] ++;//b的入度+1
        }

        List<Integer> arr = topLogicalSort(graph, inDegree, numCows);
        //判断输出的数组，长度不为numCows，那就是图中有环了，输出不了一个完整的拓扑顺序
        if (arr.size() == numCows) {
            int[] str = new int[numCows];
            int i = 0;
            for (int j = arr.size() - 1; j >= 0; j--)
                str[i++] = arr.get(j);
            return str;
        }
        return new int[0];
    }
}