- 31.0%

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?

1 | For example: |

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1 | 2, [[1,0],[0,1]] |

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.

Hints:

- This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
- Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- Topological sort could also be done via BFS.

https://discuss.leetcode.com/topic/17273/18-22-lines-c-bfs-dfs-solutions

18-22 lines C++ BFS/DFS Solutions

As suggested by the hints, this problem is equivalent to detecting a cycle in the graph represented by prerequisites. Both BFS and DFS can be used to solve it using the idea of topological sort. If you find yourself unfamiliar with these concepts, you may refer to their wikipedia pages. Specifically, you may only need to refer to the link in the third hint to solve this problem.

Since pair<int, int> is inconvenient for the implementation of graph algorithms, we first transform it to a graph. If course u is a prerequisite of course v, we will add a directed edge from node u to node v.

BFS

BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we have found one. We set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of all its neighbors by 1. This process will be repeated for n (number of nodes) times. If we have not returned false, we will return true.

1 | class Solution { |

DFS

For DFS, it will first visit a node, then one neighbor of it, then one neighbor of this neighbor… and so on. If it meets a node which was visited in the current process of DFS visit, a cycle is detected and we will return false. Otherwise it will start from another unvisited node and repeat this process till all the nodes have been visited. Note that you should make two records: one is to record all the visited nodes and the other is to record the visited nodes in the current DFS visit.

The code is as follows. We use a vector

1 | class Solution { |

https://discuss.leetcode.com/topic/13441/bfs-topological-sort-and-dfs-finding-cycle-by-c

BFS(Topological Sort) and DFS(Finding cycle) by C++

- BFS(Topological Sort)

1 | bool canFinish(int numCourses, vector<vector<int>>& prerequisites) |

- DFS(Finding cycle)

1 | bool canFinish(int numCourses, vector<vector<int>>& prerequisites) |

https://discuss.leetcode.com/topic/18734/c-clean-code-for-dfs-solution-with-simple-comments

C++ clean code for DFS solution with simple comments

1 | bool canFinish(int numCourses, vector<pair<int, int>>& prer) { |

https://discuss.leetcode.com/topic/13412/python-20-lines-dfs-solution-sharing-with-explanation

Python 20 lines DFS solution sharing with explanation

1 | def canFinish(self, numCourses, prerequisites): |

- if node v has not been visited, then mark it as 0.
- 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.
- 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.

References: daoluan.net

AC Python topological sort 52 ms solution, O(V + E) time and O(V + E) space

1 | def canFinish(self, n, pres): |

The topological sort is natural for this problem. We always take the courses with no unstudied prereqs and so on until no more courses we can take. The oud[i] is the number of prereqs for course i and indegree keep a list of courses require course i.