Question
Formatted question description: https://leetcode.ca/all/207.html
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?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0.
So it is possible.
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.
click to show more hints.
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.
@tag-graph
Algorithm
Kahn’s Algorithms:
https://en.wikipedia.org/wiki/Topological_sorting#Kahn’s_algorithm
BFS based,
- start from with vertices with 0 incoming edge,insert them into list S,at the same time we remove all their outgoing edges,
- after that find new vertices with 0 incoming edges and go on.
Tarjan’s Algorithms:
https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm DFS based,
- loop through each node of the graph in an arbitrary order,
- initiating a depth-first search that terminates when it hits any node that has already been visited
- since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node).
Code
Java
-
public class Course_Schedule { public class Solution_bfs { public boolean canFinish(int numCourses, int[][] prerequisites) { // Kahn's Algorithm if(numCourses <= 0) { return false; } if(prerequisites == null || prerequisites.length == 0) { return true; } int[] inDegree = new int[numCourses]; // 1. setup indgree count for(int[] edge : prerequisites) { inDegree[edge[0]]++; } Queue<Integer> queue = new LinkedList<>(); // 2. start from node with no indgree, i.e. no prerquisites for this course for(int i = 0; i < inDegree.length; i++) { if(inDegree[i] == 0) { queue.offer(i); } } List<Integer> result = new ArrayList<>(); while(!queue.isEmpty()) { int currentCourse = queue.poll(); result.add(currentCourse); for(int[] edge : prerequisites) { if(edge[1] == currentCourse) { // if a course requires current course if(--inDegree[edge[0]] == 0) // -1, since current course is taken, and fulfill course edge[0] queue.offer(edge[0]); } } } return result.size() == numCourses; } } public class Solution_dfs { public boolean canFinish(int numCourses, int[][] prerequisites) { if(prerequisites == null || prerequisites.length < 2) { return true; } // 0 for not visited,1 for globally visited,-1 for visisted AND on current path int[] isVisited = new int[numCourses]; List<List<Integer>> graph = new ArrayList<>(); // 1. build graph for (int i = 0; i < numCourses; i++) { graph.add(new ArrayList<>()); } for (int[] each: prerequisites) { graph.get(each[1]).add(each[0]); } // 2. dfs for (int i = 0; i < numCourses; i++) { if (!dfs(i, isVisited, graph)) { return false; } } return true; } private boolean dfs(int courseIndex, int[] isVisited, List<List<Integer>> graph) { if (isVisited[courseIndex] == 1) { return true; } if (isVisited[courseIndex] == -1) { return false; // cycle found } isVisited[courseIndex] = -1; for (Integer next: graph.get(courseIndex)) { if(!dfs(next, isVisited, graph)) { return false; } } isVisited[courseIndex] = 1; return true; } } }
-
// OJ: https://leetcode.com/problems/course-schedule/ // Time: O(V + E) // Space: O(V + E) class Solution { public: bool canFinish(int n, vector<vector<int>>& E) { vector<vector<int>> G(n); vector<int> indegree(n); for (auto &e : E) { G[e[1]].push_back(e[0]); ++indegree[e[0]]; } queue<int> q; for (int i = 0; i < n; ++i) { if (indegree[i] == 0) q.push(i); } while (q.size()) { int u = q.front(); q.pop(); --n; for (int v : G[u]) { if (--indegree[v] == 0) q.push(v); } } return n == 0; } };
-
class Solution(object): def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ def dfs(start, parent, visited, graph): visited[start] = 1 for nbr in graph[start]: if visited[nbr] == 1: return False if dfs(nbr, start, visited, graph) == False: return False visited[start] = 2 return True graph = [[] for _ in range(0, numCourses)] for pre in prerequisites: start, end = pre graph[start].append(end) visited = [0 for _ in range(0, numCourses)] for pre in prerequisites: start, end = pre if visited[start] == 0: if dfs(start, None, visited, graph) == False: return False return True