大家好,我是开车的阿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!