Problem description:

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.

Solution1 DFS:

We can use DFS to solve this question. From above example, Input: 2, [[1,0],[0,1]], we can see that if the graph contains a cycle, we can not finish all the courses.

First of all, let’s see how we generate a graph. we can use a vector<unordered_set> to do so. Every index stores the courses that can be taken after finish the index course.

Second, we need to traverse the graph and find if there’s any cycle. The idea of finding a cycle is to record the nodes that we’ve already traversed on current path. If we encounter a node that we’ve already traversed, then it must contains a cycle in the graph. After current path is checked, reset it to false.

Third, another visited array to store which node is already traversed. help to save time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        /*
        1. create a graph for dfs
        2. if we can find a cycle, then we can not finish all courses. 
        */
        vector<unordered_set<int>> graph(numCourses);
        for(auto n: prerequisites){
            graph[n.second].insert(n.first); 
            // [1, 0]: To take course 1 you should have finished course 0
            // So we need an edge from 0->1, because we need to get to 0 then 1
        }
        vector<bool> visited(numCourses, false), onpath(numCourses, false); //the second one is to check cycle
        for(int i= 0; i< numCourses; i++){
            if(!visited[i] && dfscycle(graph, visited, onpath, i))
                return false;
        }
        return true;
    }
    
    bool dfscycle(vector<unordered_set<int>>& graph, vector<bool>& visited, vector<bool>& onpath, int index){
        if(visited[index]) return false; //already traversed this node in big picture
        
        onpath[index]= visited[index]= true; //set to true denoted that we traverse this node
        for(auto neighbor: graph[index]){ //check all next level as node index is the prerequist
            if(onpath[neighbor] || dfscycle(graph, visited, onpath, neighbor)) 
                return true;
            //1. onpath[neighbor] is true, means that this neighbor is already in this subpath, so we have a cycle
            //2. dfscycle, go further and find a cycle in subpath
        }
        onpath[index]= false; //reset to false
        return false;
    }
};

Python DFS

  1. if node v has not been visited, then mark it as 0.
  2. if node v is being visited, then mark it as -1. If we find a vertex marked as -1 in DFS, then their is a ring.
  3. if node v has been visited, then mark it as 1. If a vertex was marked as 1, then no ring contains v or its successors.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:            
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Idea is to find if there's any cycle 
        visited = [0] * numCourses
        # state of visited: 
        # 0,  not visited
        # 1,  visited
        # -1, visting
        graph = [[] for _ in range(numCourses)]
        
        for x, y in prerequisites:
            graph[y].append(x)
        
        for i in range(numCourses):
            if not self.dfsCycle(graph, visited, i):
                return False
        return True
        
    def dfsCycle(self, graph, visited, i):
        if visited[i] == -1:
            return False
        if visited[i] == 1:
            return True
        # change the state to visiting, if we somehow get to this node again, then there's a cycle
        visited[i] = -1
        for course in graph[i]:
            if not self.dfsCycle(graph, visited, course):
                return False
        visited[i] = 1
        return True

Solution2 BFS:

The BFS solution is to apply topological sort. The idea is to check if every node does not have any indegree after we traverse the graph.

First, we need to generate a graph. Pretty similar to DFS solution above.
Second, we need a indegree array, size is numCourses. Add one if a course have prerequisite.
After calculated the indegree, some of the node might not have any indegree, so we start to traverse from them.

Third, BFS. If a node’s indegree becomes zero, then we need to push it into the queue.
Finally, check indegree array to see if all zero.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //BFS
        /*
        1. calculate indegree for every node
        2. BFS, push every node with indegree 0 into queue
        3. check if every node has indegree 0
        */
        
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        for(auto n: prerequisites){
            indegree[n.first]++;
            graph[n.second].push_back(n.first);
        }
        
        queue<int> q;
        for(int i= 0; i< numCourses; i++){
            if(indegree[i] == 0) q.push(i);
        }
        
        while(!q.empty()){
            auto tmp= q.front(); q.pop();
            
            for(int i= 0; !graph[tmp].empty() && i< graph[tmp].size(); i++){
                if(--indegree[graph[tmp][i]] == 0) q.push(graph[tmp][i]);
            }
        }
        
        for(int i= 0; i< numCourses; i++){
            if(indegree[i] != 0) return false;
        }
        
        return true;
        
    }
};

Solution Python BFS topological sort

The idea is to build graph, then add every node’s prerequisites to a set.
Notice the graph is build to find if I complete course y then what I could move next x.
But the todo is if want to take x, what y should take.

  1. Walk through the node that have no prerequisites first
  2. Remove node n from other’s todo, because node n is completed.
  3. When we find other node X have todo with length 0, ie: nothing else to do after complete node n, then we add X to queue.
  4. Finally, check if todo is empty. If it’s not, then there’s a cycle.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:            
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        todo = {i: set() for i in range(numCourses)} 
        graph = defaultdict(set)
        for i,j in prerequisites:
            todo[i].add(j)
            graph[j].add(i)
        q = deque([])
        for k,v in todo.items():
            if len(v) == 0:
                q.append(k)
        while q:
            n = q.popleft()
            for i in graph[n]:
                todo[i].remove(n)
                if len(todo[i]) == 0:
                    q.append(i)
            todo.pop(n)
        return not todo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # build graph to know who's neighbor of each course
        # build indegree to know how many prerequisites has completed for a course
        # use BFS to start from node where indegree = 0
        graph = defaultdict(list)
        indegree = [0 for i in range(numCourses)]
        for pre in prerequisites:
            graph[pre[1]].append(pre[0])
            indegree[pre[0]] += 1
        
        q = deque()
        for i in range(len(indegree)):
            if indegree[i] == 0:
                q.append(i)
        
        while q:
            node = q.popleft()
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)
            
        return not any(indegree[i] != 0 for i in range(len(indegree)))

reference:
https://www.youtube.com/watch?v=zkTOIVUdW-I
https://goo.gl/iN1qG3