|
5 | 5 | import java.util.Set;
|
6 | 6 |
|
7 | 7 | /**There are a total of n courses you have to take, labeled from 0 to n - 1.
|
8 |
| -
|
9 |
| - 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] |
10 |
| -
|
| 8 | + Some courses may have prerequisites, for example to take course 0 you have to first take course 1, |
| 9 | + which is expressed as a pair: [0,1] |
11 | 10 | Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
|
12 | 11 |
|
13 | 12 | For example:
|
14 |
| -
|
15 | 13 | 2, [[1,0]]
|
16 |
| - There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. |
| 14 | + There are a total of 2 courses to take. |
| 15 | + To take course 1 you should have finished course 0. So it is possible. |
17 | 16 |
|
18 | 17 | 2, [[1,0],[0,1]]
|
19 |
| - 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. |
| 18 | + There are a total of 2 courses to take. |
| 19 | + To take course 1 you should have finished course 0, |
| 20 | + and to take course 0 you should also have finished course 1. So it is impossible. |
20 | 21 |
|
21 | 22 | Note:
|
22 | 23 | The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
|
|
27 | 28 | 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.
|
28 | 29 | Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
|
29 | 30 | Topological sort could also be done via BFS.*/
|
30 |
| -public class CourseSchedule { |
| 31 | +public class _207 { |
31 | 32 |
|
32 | 33 | public boolean canFinish(int numCourses, int[][] prerequisites) {
|
33 | 34 | int[] indegree = new int[numCourses];
|
|
0 commit comments