# 207. Course Schedule

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.

# Solution

Approach 1: the problem is equivalent to detecting cycles in directed graph -- linearlization problem. The first algorithm to solve is by DFS.

Approach 2: the second algorithm to solve the linearlization problem is BFS -- record the indegrees of each node, peel off layers of nodes that has indegree == 0.

# Code (Python)

Approach 1:

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # idea: DFS, and mark nodes as in progress while searching in depth
        edges = {course: [] for course in range(numCourses)}
         # edges flow from advanced courses to prereq
        for course, prereq in prerequisites:
            edges[course].append(prereq)
        
        # -1: not visited, 1: visited, 0: visiting
        visited = [-1] * numCourses
        for course in range(numCourses):
            if not self._search(course, edges, visited):
                return False
        
        return True
    
    def _search(self, node, edges, visited):
        if visited[node] == 1:
            return True
        if visited[node] == 0: # found a cycle!
            return False

        visited[node] = 0
        for neighbor in edges[node]:
            if not self._search(neighbor, edges, visited):
                return False
        visited[node] = 1
        
        return True

Approach 2:

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # idea: record the indegrees of each node, peel off layers of nodes that has indegree == 0
        edges = {course: [] for course in range(numCourses)}
        indegree = {course: 0 for course in range(numCourses)}
        layer = set([course for course in range(numCourses)]) # nodes with indegree == 0
        # edges flow from prereq to advanced courses
        for course, prereq in prerequisites:
            edges[prereq].append(course)
            indegree[course] += 1
            if course in layer:
                layer.remove(course)
        
        num_visited = 0
        layer = deque(layer)
        while layer:
            node = layer.popleft()
            num_visited += 1
            for neighbor in edges[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    layer.append(neighbor)
        
        if num_visited == numCourses:
            return True
        return False

# Code (C++)

Approach 1:

// DFS.
class Solution {
private:
    unordered_map<int,vector<int>> neighbors;
    vector<bool> visitedPerm;
    vector<bool> visitedTemp;
    vector<bool> cycling;
    bool canFinishCourse(int course) {
        if (visitedPerm[course])
            return !cycling[course];
        if (visitedTemp[course])
            return false;
        visitedTemp[course] = true;
        for (auto v : neighbors[course])
        {
            if (!canFinishCourse(v))
            {
                cycling[course] = true;
                break;
            }
        }
        visitedTemp[course] = false;
        visitedPerm[course] = true;
        return !cycling[course];
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for (auto pair : prerequisites)
        {
            neighbors[pair[0]].push_back(pair[1]);
        }
        visitedPerm = vector<bool>(numCourses, false);
        visitedTemp = vector<bool>(numCourses, false);
        cycling = vector<bool>(numCourses, false);
        for (int i = 0; i < numCourses; ++i)
        {
            if (!canFinishCourse(i))
                return false;
        }
        return true;
    }
};

Approach 2:

// BFS.
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        unordered_map<int,int> indegree;
        unordered_map<int,vector<int>> edge;
        for (int i = 0; i < numCourses; ++i)
        {
            indegree[i] = 0;
        }
        for (auto it : prerequisites)
        {
            int curr = it.first;
            int prev = it.second;
            indegree[curr]++;
            edge[prev].push_back(curr);
        }
        while (!empty(indegree))
        {
            unordered_map<int,int>::iterator it;
            for (it = indegree.begin(); it != indegree.end(); ++it)
            {
                if (it->second == 0)
                    break;
            }
            if (it == indegree.end())
                return false;
            int curr = it->first;
            indegree.erase(it);
            for (auto prev : edge[curr])
            {
                indegree[prev]--;
            }
        }
        return true;
    }
};