# Course Schedule

`Graph`, `Depth-first Search`, `Breadth-first Search`, `Topological Sorting`

Medium

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:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

2. You may assume that there are no duplicate edges in the input prerequisites.

## Analysis

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])) {
}
}
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) {
}
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)

``````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++) {
}
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) {
}
}
}``````

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]] ++ ;
}

Queue queue = new LinkedList();
for(int i = 0; i < degree.length; i++){
if (degree[i] == 0) {
}
}

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) {
}
}
}

return count == numCourses;
}
}``````

## Reference

https://www.jiuzhang.com/solution/course-schedule

https://blog.csdn.net/ljiabin/article/details/45846837