首页 > 代码库 > 207. Course Schedule
207. Course Schedule
题目:
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.
click to show more 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.
链接: http://leetcode.com/problems/course-schedule/
6/28/2017
有向图,先求indegree,然后每次从queue当中取出来indegree为0的课程,最后看queue当中是否为空。
Kahn‘s Algorithms
1 public class Solution { 2 public boolean canFinish(int numCourses, int[][] prerequisites) { 3 // calculate indegree 4 int[] indegree = new int[numCourses]; 5 List<List<Integer>> graph = new ArrayList<>(); 6 for (int i = 0; i < numCourses; i++) { 7 graph.add(new ArrayList<Integer>()); 8 } 9 for (int i = 0; i < prerequisites.length; i++) { 10 indegree[prerequisites[i][0]]++; 11 graph.get(prerequisites[i][1]).add(prerequisites[i][0]); 12 } 13 14 Queue<Integer> q = new LinkedList<Integer>(); 15 // add indegree == 0 vertex to queue 16 for (int i = 0; i < numCourses; i++) { 17 if (indegree[i] == 0) { 18 q.add(i); 19 } 20 } 21 22 int counter = 0; 23 while (!q.isEmpty()) { 24 int vertex = q.poll(); 25 counter++; 26 // decrease all adjacent vertex indegree by 1 27 int adjacentVertexLength = graph.get(vertex).size(); 28 for (int i = 0; i < adjacentVertexLength; i++) { 29 int w = graph.get(vertex).get(i); 30 indegree[w]--; 31 // check if new indegree is 0 32 if (indegree[w] == 0) { 33 q.add(w); 34 } 35 } 36 } 37 38 return counter == numCourses; 39 } 40 }
这道题很久之前做的,思路已经忘记了,具体题解可以参考:
http://www.cnblogs.com/yrbbest/p/4493547.html
求Course Schedule,等同问题是有向图检测环,vertex是course, edge是prerequisite。我觉得一般会使用Topological Sorting拓扑排序来检测。一个有向图假如有环则不存在Topological Order。一个DAG的Topological Order可以有大于1种。 常用的Topological Sorting算法有两种
- Kahn‘s Algorithms (wiki): BFS based, start from with vertices with 0 incoming edge,insert them into list S,at the same time we remove all their outgoing edges,after that find new vertices with 0 incoming edges and go on. 详细过程见Reference里Brown大学的课件。
- Tarjan‘s Algorithms (wiki): DFS based, loop through each node of the graph in an arbitrary order,initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node). 详细过程见Reference里 NYU的课件。
别人的解法
https://discuss.leetcode.com/topic/17273/18-22-lines-c-bfs-dfs-solutions
https://discuss.leetcode.com/topic/13854/easy-bfs-topological-sort-java
https://discuss.leetcode.com/topic/25964/ac-python-topological-sort-52-ms-solution-o-v-e-time-and-o-v-e-space
更多讨论
https://discuss.leetcode.com/category/215/course-schedule
207. Course Schedule