Leetcode 207. Course Schedule

xiaoxiao2021-02-28  17

原题:

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.You may assume that there are no duplicate edges in the input prerequisites. Hints: This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.Topological sort could also be done via BFS. 解决方法:

典型的图论的处理问题,DFS和BFS都可以实现,这里实现了BFS的方法。

-首先根据课程之间的关系建立图的节点;

- 根据图的节点计算每一节点的入度;

-循环从图中寻找入度为0的点,如果没有,说明路径不通,直接返回false。将与该节点有关的节点的入度减一。

代码: typedef unordered_set<int> Node; typedef vector<Node> Graph; typedef vector<int> Degree; Graph makeGraph(int numCourses, vector<pair<int, int>>& prerequisites){ Graph graph(numCourses); for(auto pre: prerequisites) graph[pre.second].insert(pre.first); return graph; } Degree makeDegree(Graph& graph){ Degree d(graph.size(), 0); for(auto neighbors: graph){ for(auto n: neighbors) d[n]++; } return d; } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { Graph graph = makeGraph(numCourses, prerequisites); Degree d = makeDegree(graph); for(int i = 0; i < numCourses; i++){ int j = 0; for(j = 0; j < numCourses;j++){ if (!d[j]) break; } if (j >= numCourses) return false; d[j] = -1; for(auto n: graph[j]) d[n]--; } return true; }
转载请注明原文地址: https://www.6miu.com/read-2350035.html

最新回复(0)