|
7 | 7 | import java.util.Set;
|
8 | 8 |
|
9 | 9 | /**There are a total of n courses you have to take, labeled from 0 to n - 1.
|
| 10 | + Some courses may have prerequisites, for example to take course 0 you have to first take course 1, |
| 11 | + which is expressed as a pair: [0,1] |
| 12 | + Given the total number of courses and a list of prerequisite pairs, |
| 13 | + return the ordering of courses you should take to finish all courses. |
10 | 14 |
|
11 |
| - 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] |
12 |
| -
|
13 |
| - Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. |
14 |
| -
|
15 |
| - There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. |
| 15 | + There may be multiple correct orders, |
| 16 | + you just need to return one of them. |
| 17 | + If it is impossible to finish all courses, return an empty array. |
16 | 18 |
|
17 | 19 | For example:
|
18 | 20 |
|
19 | 21 | 2, [[1,0]]
|
20 |
| - There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] |
| 22 | + There are a total of 2 courses to take. |
| 23 | + To take course 1 you should have finished course 0. So the correct course order is [0,1] |
21 | 24 |
|
22 | 25 | 4, [[1,0],[2,0],[3,1],[3,2]]
|
23 |
| - There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3]. |
| 26 | + There are a total of 4 courses to take. |
| 27 | + To take course 3 you should have finished both courses 1 and 2. |
| 28 | + Both courses 1 and 2 should be taken after you finished course 0. |
| 29 | + So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3]. |
24 | 30 |
|
25 | 31 | Note:
|
26 | 32 | The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
|
|
31 | 37 | This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
|
32 | 38 | Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
|
33 | 39 | Topological sort could also be done via BFS.*/
|
34 |
| -public class CourseScheduleII { |
| 40 | +public class _210 { |
35 | 41 |
|
36 | 42 | public int[] findOrder(int numCourses, int[][] prerequisites) {
|
37 | 43 | int[] inDegree = new int[numCourses];
|
|
0 commit comments