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

知识点：拓扑排序

思路：这些数组可以看成一个有向图的边到边的路，也就是矩阵存储图的表示，

拓扑排序则是可以判断图中是否存在环，并且输出一条不存在环的路

拓扑排序思路：

1.将入度为0的节点添加到队列

2.终止条件，队列是否为空，

3.紧接着，将出队列的顶点，判断其边，并且度数为0的边再次入队

核心思想还是bfs，和bfs遍历图的所有节点，以及bfs层序遍历二叉树一个道理

编程语言：java

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

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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numCows int整型
     * @param feedOrders int整型二维数组
     * @return bool布尔型
     */
    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 boolean canFeedAllCows (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)
            return true;
        return false;
    }
}