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?
Example 1:
Input: 2, [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]] Output: false Explanation: 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.
想法如下
- 這題本質上，是一題有向圖(Directed Acyclic Graph) 的問題
- 如果從題目給的條件所建出來的DAG是有 cycle 在裡面的話，那麼就不可能完成所有的課程
- 在 DAG，可以用 topological sorting 的方式，來檢驗 DAG 是不是有 cycle。只要有 cycle，那麼 topological sorting 就不可能會歷遍到所有的節點
Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public boolean canFinish(int numCourses, int[][] prerequisites) { | |
| int[][] DAG = new int[numCourses][numCourses]; | |
| int[] indegree = new int[numCourses]; | |
| //>> calculate indegree of each vertex and construct a DAG | |
| int course, preCourse; | |
| for(int i = 0; i < prerequisites.length; i++) { | |
| course = prerequisites[i][0]; | |
| preCourse = prerequisites[i][1]; | |
| DAG[preCourse][course] = 1; | |
| indegree[course]++; | |
| } | |
| //>> find all vertice with 0 indegree | |
| Queue<Integer> queue = new LinkedList<>(); | |
| for(int i = 0; i < numCourses; i++) { | |
| if(indegree[i] == 0) { | |
| queue.offer(i); | |
| } | |
| } | |
| //>> topological sort | |
| int cnt = 0; | |
| while(!queue.isEmpty()) { | |
| course = queue.poll(); | |
| cnt++; | |
| for(int i = 0; i < numCourses; i++) { | |
| if(DAG[course][i] == 1) { | |
| indegree[i]--; | |
| if(indegree[i] == 0) { | |
| queue.offer(i); | |
| } | |
| } | |
| } | |
| } | |
| return cnt == numCourses; | |
| } | |
| } |
Kotlin
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean { | |
| val graph = Array(numCourses) { BooleanArray(numCourses) {false} } | |
| val requirement = IntArray(numCourses) {0} | |
| var course: Int | |
| var preCourse: Int | |
| for(i in prerequisites.indices) { | |
| course = prerequisites[i][0] | |
| preCourse = prerequisites[i][1] | |
| graph[preCourse][course] = true | |
| ++requirement[course] | |
| } | |
| //>> find course without requirement | |
| val queue = mutableListOf<Int>() | |
| for(i in requirement.indices) { | |
| if(requirement[i] == 0) { | |
| queue.add(i) | |
| } | |
| } | |
| var cnt = 0 | |
| while(queue.isNotEmpty()) { | |
| ++cnt | |
| course = queue.removeAt(0) | |
| for(i in 0 until numCourses) { | |
| if(graph[course][i]) { | |
| graph[course][i] = false | |
| --requirement[i] | |
| if(requirement[i] == 0) { | |
| queue.add(i) | |
| } | |
| } | |
| } | |
| } | |
| return cnt == numCourses | |
| } | |
| } |
沒有留言:
張貼留言