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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numCows int整型
     * @param feedOrders int整型二维数组
     * @return bool布尔型
     */
    public boolean canFeedAllCows (int numCows, int[][] feedOrders) {
        // write code here
        Map<Integer, List<Integer>> graph = new HashMap<>();//graph 用于表示有向图的邻接表
        int[] inDegree = new int[numCows];//记录每个节点的入度

        // 初始化邻接表和入度数组
        for (int i = 0; i < numCows; i++) {
            graph.put(i, new ArrayList<>());
        }

        // 构建有向图和入度数组
        for (int[] order : feedOrders) {
            int from = order[1]; //有向边的起始节点
            int to = order[0]; //有向边的结束节点
            graph.get(from).add(to); //表示从节点 from 指向节点 to
            inDegree[to]++;
        }

        // 使用拓扑排序判断是否存在环路
        //将入度为0的节点加入队列
        List<Integer> queue = new ArrayList<>();
        for (int i = 0; i < numCows; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int current = queue.remove(0);//取出队列第一个元素
            for (int neighbor : graph.get(current)) {
                inDegree[neighbor]--;//将当前节点的邻节点入度减一
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        // 如果所有节点的入度都为0，说明不存在环路
        for (int degree : inDegree) {
            if (degree != 0) {
                return false;
            }
        }

        return true;
    }
}

知识点分析

1.有向图

2.邻接表

3.拓扑排序

解题思路分析

核心解题思路是使用拓扑排序来判断是否存在环路，从而确定是否可以按照喂养顺序完成所有牛的喂养。

1.构建有向图和入度数组： 遍历喂养顺序数组 feedOrders，将其解析为有向图的邻接表表示，同时维护每个节点的入度数组。

2.拓扑排序： 使用队列进行拓扑排序，初始将所有入度为 0 的节点加入队列。然后，不断地从队列中取出节点，更新其邻接节点的入度，并将新的入度为 0 的节点加入队列。

3.检查是否存在环路： 遍历入度数组，如果存在任何节点的入度不为 0，说明存在环路，返回 false；否则，返回 true。