Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/207.html
There are a total of numCourses
courses you have to take, labeled from 0
to numCourses - 1
. You are given an array prerequisites
where prerequisites[i] = [ai, bi]
indicates that you must take course bi
first if you want to take course ai
.
- For example, the pair
[0, 1]
, indicates that to take course0
you have to first take course1
.
Return true
if you can finish all courses. Otherwise, return false
.
Example 1:
Input: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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.
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
- All the pairs prerequisites[i] are unique.
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
-
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; } } } ############ class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<Integer>[] g = new List[numCourses]; Arrays.setAll(g, k -> new ArrayList<>()); int[] indeg = new int[numCourses]; for (var p : prerequisites) { int a = p[0], b = p[1]; g[b].add(a); ++indeg[a]; } Deque<Integer> q = new ArrayDeque<>(); for (int i = 0; i < numCourses; ++i) { if (indeg[i] == 0) { q.offer(i); } } int cnt = 0; while (!q.isEmpty()) { int i = q.poll(); ++cnt; for (int j : g[i]) { if (--indeg[j] == 0) { q.offer(j); } } } return cnt == numCourses; } }
-
// 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; } };
-
''' >>> from collections import defaultdict >>> a = defaultdict(int) >>> a defaultdict(<type 'int'>, {}) >>> >>> a['hehehe'] 0 >>> a defaultdict(<type 'int'>, {'hehehe': 0}) >>> a = defaultdict(list) >>> a defaultdict(<type 'list'>, {}) >>> a['hehehe'] [] >>> a defaultdict(<type 'list'>, {'hehehe': []}) ''' class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: g = defaultdict(list) indeg = [0] * numCourses for a, b in prerequisites: g[b].append(a) indeg[a] += 1 cnt = 0 q = deque([i for i, v in enumerate(indeg) if v == 0]) while q: i = q.popleft() cnt += 1 for j in g[i]: indeg[j] -= 1 if indeg[j] == 0: q.append(j) return cnt == numCourses ############ 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
-
func canFinish(numCourses int, prerequisites [][]int) bool { g := make([][]int, numCourses) indeg := make([]int, numCourses) for _, p := range prerequisites { a, b := p[0], p[1] g[b] = append(g[b], a) indeg[a]++ } q := []int{} for i, v := range indeg { if v == 0 { q = append(q, i) } } cnt := 0 for len(q) > 0 { i := q[0] q = q[1:] cnt++ for _, j := range g[i] { indeg[j]-- if indeg[j] == 0 { q = append(q, j) } } } return cnt == numCourses }
-
function canFinish(numCourses: number, prerequisites: number[][]): boolean { let g = Array.from({ length: numCourses }, () => []); let indeg = new Array(numCourses).fill(0); for (let [a, b] of prerequisites) { g[b].push(a); ++indeg[a]; } let q = []; for (let i = 0; i < numCourses; ++i) { if (!indeg[i]) { q.push(i); } } let cnt = 0; while (q.length) { const i = q.shift(); ++cnt; for (let j of g[i]) { if (--indeg[j] == 0) { q.push(j); } } } return cnt == numCourses; }
-
public class Solution { public bool CanFinish(int numCourses, int[][] prerequisites) { var g = new List<int>[numCourses]; for (int i = 0; i < numCourses; ++i) { g[i] = new List<int>(); } var indeg = new int[numCourses]; foreach (var p in prerequisites) { int a = p[0], b = p[1]; g[b].Add(a); ++indeg[a]; } var q = new Queue<int>(); for (int i = 0; i < numCourses; ++i) { if (indeg[i] == 0) q.Enqueue(i); } var cnt = 0; while (q.Count > 0) { int i = q.Dequeue(); ++cnt; foreach (int j in g[i]) { if (--indeg[j] == 0) q.Enqueue(j); } } return cnt == numCourses; } }