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

京公网安备 11010502036488号