Course Schedule
Graph, Depth-first Search, Breadth-first Search, Topological Sorting
Medium
There are a total of n courses you have to take, labeled from0ton-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.
Analysis
此题考虑课程依赖关系是否能满足，其实抽象来看，课程的依赖关系其实是有向图的边edge，那么问题的内核其实就是这个有向图是否有环，如果无环，则依赖关系可以成立，也就是DAG （有向无环图）。判定是否为DAG，则可以用拓扑排序Topological Sorting。
https://www.youtube.com/watch?v=M6SBePBMznU
拓扑排序 = 顶点染色 + 记录顺序
这里只需要顶点染色即可。
DFS - 需要先遍历叶子节点，再遍历根节点，因此可以看成是post-order
Solution
Topological Sorting - HashMap - DFS - (9ms 83.11% AC)
class Solution {
private HashMap<Integer, ArrayList<Integer>> graph;
public boolean canFinish(int numCourses, int[][] prerequisites) {
graph = new HashMap<Integer, ArrayList<Integer>>();
// states: 0 = unknown, 1 = visiting, 2 = visited
int[] visit = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.put(i, new ArrayList<Integer>());
}
for (int[] p : prerequisites) {
if (graph.containsKey(p[0])) {
graph.get(p[0]).add(p[1]);
}
}
for (int i = 0; i < numCourses; i++) {
if (dfs(i, visit)) return false;
}
return true;
}
private boolean dfs(int cur, int[] v) {
if (v[cur] == 1) return true;
if (v[cur] == 2) return false;
v[cur] = 1;
for (int i = 0; i < graph.get(cur).size(); i++) {
if (dfs(graph.get(cur).get(i), v)) return true;
}
v[cur] = 2;
return false;
}
}*Topological Sort - DFS - Improved - ArrayList[] - (5ms 99.81% AC)
class Solution {
private ArrayList[] graph;
public boolean canFinish(int numCourses, int[][] prerequisites) {
graph = new ArrayList [numCourses];
// states: 0 = unknown, 1 = visiting, 2 = visited
int[] visit = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList < Integer > ();
}
for (int[] p: prerequisites) {
graph[p[0]].add(p[1]);
}
for (int i = 0; i < numCourses; i++) {
if (dfsCyclic(i, visit)) return false;
}
return true;
}
private boolean dfsCyclic(int cur, int[] v) {
if (v[cur] == 1) return true;
if (v[cur] == 2) return false;
v[cur] = 1;
for (int i = 0; i < graph[cur].size(); i++) {
if (dfsCyclic((int) graph[cur].get(i), v)) return true;
}
v[cur] = 2;
return false;
}
}Topological Sort - OO Style - DFS (8ms 87.81% AC)
Modified from https://leetcode.com/problems/course-schedule/discuss/58713/OO-easy-to-read-java-solution
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Course[] courses = new Course[numCourses];
for (int i = 0; i < numCourses; i++) {
courses[i] = new Course();
}
for (int i = 0; i < prerequisites.length; i++) {
courses[prerequisites[i][0]].add(courses[prerequisites[i][1]]);
}
for (int i = 0; i < numCourses; i++) {
if (isCyclic(courses[i])) return false;
}
return true;
}
private boolean isCyclic(Course cur) {
if (cur.tested) return false;
if (cur.visited) return true;
cur.visited = true;
for (Course c: cur.pre) {
if (isCyclic(c)) {
return true;
}
}
cur.tested = true;
return false;
}
class Course {
boolean visited = false; // being visited
boolean tested = false; // tested if cyclic
List < Course > pre = new ArrayList < Course > ();
public void add(Course c) {
pre.add(c);
}
}
}BFS
public class Solution {
/**
* @param numCourses a total of n courses
* @param prerequisites a list of prerequisite pairs
* @return true if can finish all courses or false
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
// Write your code here
List[] edges = new ArrayList[numCourses];
int[] degree = new int[numCourses];
for (int i = 0;i < numCourses; i++)
edges[i] = new ArrayList<Integer>();
for (int i = 0; i < prerequisites.length; i++) {
degree[prerequisites[i][0]] ++ ;
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
Queue queue = new LinkedList();
for(int i = 0; i < degree.length; i++){
if (degree[i] == 0) {
queue.add(i);
}
}
int count = 0;
while(!queue.isEmpty()){
int course = (int)queue.poll();
count ++;
int n = edges[course].size();
for(int i = 0; i < n; i++){
int pointer = (int)edges[course].get(i);
degree[pointer]--;
if (degree[pointer] == 0) {
queue.add(pointer);
}
}
}
return count == numCourses;
}
}Reference
https://www.jiuzhang.com/solution/course-schedule
Last updated
Was this helpful?