郑州广告公司网站建设,江门移动网站建设多少钱,重新安wordpress网站,阜阳企业网站推广思路#xff1a;这是一道拓扑排序问题#xff0c;拓扑排序听起来可能有点复杂#xff0c;但实际上它是个相当直观的概念。想象一下#xff0c;你有很多事情要做#xff0c;但有些事情必须在另一些事情完成之后才能开始#xff0c;就像你得先穿上袜子再穿鞋子
拓扑排序就…思路这是一道拓扑排序问题拓扑排序听起来可能有点复杂但实际上它是个相当直观的概念。想象一下你有很多事情要做但有些事情必须在另一些事情完成之后才能开始就像你得先穿上袜子再穿鞋子
拓扑排序就是把这种图中的所有任务排成一个列表让每个任务满足它的所有前置任务都在它前面。这样当你按照列表的顺序去做事就能保证每件事都在它需要的时候完成了。
实现拓扑排序
准备阶段建立入度表
想象你有一张菜单上面列出了所有要做的菜品以及它们的准备步骤。首先你要确定哪些菜品可以立即开始准备没有前置任务哪些需要等待其他食材准备好。
入度表就像是一个记录板它告诉我们每个菜品还需要多少项准备工作才能开始。如果一个菜品没有任何前置步骤它的入度就是0。
实施阶段广度优先遍历 初始化你创建了一个队列用来存放那些可以立即开始准备的菜品入度为0的节点。 处理菜品你从队列中取出一个菜品开始准备相当于从队列中出队一个节点。假设这是“洗米做饭”这一步骤完成之后所有依赖于米饭的后续菜品比如炒饭、盖浇饭的准备条件就减少了一项它们的入度各减1。 更新入度表如果因为某个菜品的完成使得其他菜品的准备条件全部满足了它们的入度变为0那么这些菜品就可以加入队列等待下一轮处理。 重复步骤继续从队列中取出菜品准备直到队列为空。每完成一个菜品出队表示一个任务完成你就在总任务数上减去1。 代码
class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {//检测这个vector数组中是否有环vectorintv;vectorintindegree(numCourses, 0);//统计入度vectorvectorintgraph(numCourses, v);//统计这个点是哪些节点的前置也就是说他为哪些节点增加了入度for (int i 0; i prerequisites.size(); i){indegree[prerequisites[i][0]];//统计入度graph[prerequisites[i][1]].push_back(prerequisites[i][0]);//prerequisites[i][1]是那些节点的前置条件}queueintq;for (int i 0; i numCourses; i){if (indegree[i] 0){q.push(i);//将入度为零的节点压入}}int res 0;while (!q.empty()){int t q.front();q.pop();res;for (int i 0; i graph[t].size(); i){indegree[graph[t][i]]--;if (indegree[graph[t][i]] 0){q.push(graph[t][i]);}}}return res numCourses;}
};
