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

题目考察的知识点

这道题目主要考察图的拓扑排序算法,以及如何判断图中是否存在环。

题目解答方法的文字分析

首先,我们需要根据给定的喂养顺序关系构建一个图,其中每个牛表示一个节点,而喂养顺序关系表示边。然后我们可以使用拓扑排序算法来判断是否存在一种喂养顺序,使得所有的牛都可以被正确喂养。

拓扑排序的思想是,从图中找到入度为0的节点(即没有前置牛需要喂养的牛),将其加入到结果序列中,并将其邻接节点的入度减1。然后继续找入度为0的节点,重复上述操作,直到所有节点都被访问过或者无法找到入度为0的节点为止。

在这个问题中,我们首先需要统计每个牛的入度,然后根据喂养顺序关系构建邻接表。接下来,我们从入度为0的节点开始进行拓扑排序,同时不断更新邻接节点的入度。最后,如果所有节点都被访问过,则表示可以按照给定的喂养顺序完成所有牛的喂养,返回true,否则返回false。

本题解析所用的编程语言

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

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numCows int整型 
     * @param feedOrders int整型vector<vector<>> 
     * @return bool布尔型
     */
    bool canFeedAllCows(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);
            }
        }
        
        int visitedCount = 0;
        while (!q.empty()) {
            int cow = q.front();
            q.pop();
            visitedCount++;
            
            for (int neighbor : graph[cow]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        return visitedCount == numCows;
    }
};

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