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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numCows int整型
     * @param feedOrders int整型二维数组
     * @return bool布尔型
     */
    public boolean canFeedAllCows (int numCows, int[][] feedOrders) {
        // write code here
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCows; i++) {
            graph.add(new ArrayList<>());
        }

        // 根据feedOrders构建邻接列表
        for (int[] feedOrder : feedOrders) {
            int cowToFeed = feedOrder[0];
            int cowToBeFedFirst = feedOrder[1];
            graph.get(cowToBeFedFirst).add(cowToFeed);
        }

        // 使用Kahn算法进行拓扑排序
        int[] inDegree = new int[numCows];
        for (List<Integer> neighbors : graph) {
            for (int neighbor : neighbors) {
                inDegree[neighbor]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCows; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int visitedCows = 0;
        while (!queue.isEmpty()) {
            int cow = queue.poll();
            visitedCows++;
            for (int neighbor : graph.get(cow)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return visitedCows == numCows;
    }
}

知识点：

列表：使用List和ArrayList来动态管理列表。

循环：使用for循环遍历数组和列表。

条件判断：使用if-else语句根据条件执行不同的代码。

布尔类型：使用boolean表示布尔类型变量，用于判断条件。

解题思路：

这个题目涉及到有向图的拓扑排序，要求判断是否可以按照给定的喂养顺序关系完成所有牛的喂养。在题目描述中，牛可以看作图中的节点，而喂养顺序关系则对应图中的有向边。

为了解决这个问题，首先需要构建有向图的表示，可以使用邻接表的方式来表示每头牛之间的喂养关系。然后，可以利用拓扑排序的方法来判断是否存在一个合理的喂养顺序，使得所有牛都能被按照规定的顺序喂养。

拓扑排序的基本思想是从图中找到入度为 0 的节点（没有依赖关系的节点），然后将这些节点从图中移除，并更新与这些节点相邻的节点的入度。这个过程会一步步地移除入度为 0 的节点，直到图中没有节点剩余，或者无法再找到入度为 0 的节点为止。

在代码中，首先构建了一个有向图的邻接表表示，然后使用 Kahn's 算法来执行拓扑排序。算法的过程是从入度为 0 的节点开始，将其加入到拓扑排序结果中，并更新与之相邻的节点的入度。这个过程会持续进行，直到所有节点都被加入拓扑排序结果或无法再找到入度为 0 的节点为止。

最后，通过判断拓扑排序结果中的节点数量是否等于总牛的数量，就可以确定是否存在一个合理的喂养顺序，使得所有牛都能按照规定的顺序被喂养。