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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目主要考察以下知识点：

1. 图的拓扑排序算法：通过构建有向图，找到满足条件的拓扑排序顺序，用来解决依赖关系问题。
2. 图的入度和邻接表：统计每个节点的入度，利用邻接表来表示图中的节点关系。
3. 判断是否存在环：通过比较最终得到的拓扑排序顺序的长度和总节点数来判断是否存在环。

题目解答方法的文字分析

这个问题就像是一群牛要按照特定顺序喂食，其中有的牛必须要在其他牛之前被喂食。我们可以用一个图来表示这种喂食关系，其中图中的节点表示牛，边表示喂食的先后顺序。

下面是一个思考过程的详细步骤：

1. 统计每头牛的入度（有多少头牛需要在它之前被喂食），并构建邻接表，表示每头牛依赖的后续牛。
2. 初始化一个队列，将所有入度为0的牛加入队列，表示这些牛没有依赖关系，可以作为起始喂食的节点。
3. 从队列中不断取出牛，将其加入喂食顺序中，并将其邻接节点的入度减1。如果邻接节点的入度变为0，将其加入队列。
4. 重复步骤3，直到队列为空。如果得到的喂食顺序的长度等于总的牛的数量，说明所有牛都可以被喂食，返回喂食顺序；否则，表示存在环，无法满足所有牛的喂食顺序，返回空数组。

接下来，就让我们通过代码来实现这个思路。

本题解析所用的编程语言

本题解析所用的编程语言是C++。

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numCows int整型 
     * @param feedOrders int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> findFeedOrderII(int numCows, vector<vector<int> >& feedOrders) {
        // 统计每个牛的入度
        vector<int> inDegree(numCows, 0);
        
        // 构建有向图
        vector<vector<int>> graph(numCows);
        for (auto& order : feedOrders) {
            int from = order[1];
            int to = order[0];
            graph[from].push_back(to);
            inDegree[to]++;
        }
        
        // 使用队列进行拓扑排序
        queue<int> q;
        for (int i = 0; i < numCows; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> feedOrder; // 存储喂养顺序
        while (!q.empty()) {
            int cow = q.front();
            q.pop();
            feedOrder.push_back(cow); // 将当前牛加入喂养顺序
            
            for (int neighbor : graph[cow]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        // 判断是否存在环
        if (feedOrder.size() != numCows) {
            return vector<int>(); // 返回空数组
        }
        
        return feedOrder;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！