|
4 | 4 | importjava.util.Iterator; |
5 | 5 | importjava.util.Set; |
6 | 6 |
|
7 | | -/** |
8 | | - * 207. Course Schedule |
9 | | - * |
10 | | - * There are a total of n courses you have to take, labeled from 0 to n - 1. |
11 | | - Some courses may have prerequisites, for example to take course 0 you have to first take course 1, |
12 | | - which is expressed as a pair: [0,1] |
13 | | - Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? |
14 | | -
|
15 | | - For example: |
16 | | - 2, [[1,0]] |
17 | | - There are a total of 2 courses to take. |
18 | | - To take course 1 you should have finished course 0. So it is possible. |
19 | | -
|
20 | | - 2, [[1,0],[0,1]] |
21 | | - There are a total of 2 courses to take. |
22 | | - To take course 1 you should have finished course 0, |
23 | | - and to take course 0 you should also have finished course 1. So it is impossible. |
24 | | -
|
25 | | - Note: |
26 | | - The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. |
27 | | - You may assume that there are no duplicate edges in the input prerequisites. |
28 | | - click to show more hints. |
29 | | -
|
30 | | - Hints: |
31 | | - 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. |
32 | | - Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort. |
33 | | - Topological sort could also be done via BFS. |
34 | | - */ |
35 | 7 | publicclass_207 { |
36 | 8 |
|
37 | 9 | publicstaticclassSolution1 { |
|