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 course 0 you have to first take course 1.
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.
Solutions
Solution 1: Topological Sorting
For this problem, we can consider the courses as nodes in a graph, and prerequisites as edges in the graph. Thus, we can transform this problem into determining whether there is a cycle in the directed graph.
Specifically, we can use the idea of topological sorting. For each node with an in-degree of $0$, we reduce the in-degree of its out-degree nodes by $1$, until all nodes have been traversed.
If all nodes have been traversed, it means there is no cycle in the graph, and we can complete all courses; otherwise, we cannot complete all courses.
The time complexity is $O(n + m)$, and the space complexity is $O(n + m)$. Here, $n$ and $m$ are the number of courses and prerequisites respectively.
usestd::collections::VecDeque;implSolution{#[allow(dead_code)]pubfncan_finish(num_course:i32,prerequisites:Vec<Vec<i32>>)->bool{letnum_course=num_courseasusize;// The graph representationletmutgraph:Vec<Vec<i32>>=vec![vec![];num_course];// Record the in degree for each nodeletmutin_degree_vec:Vec<i32>=vec![0;num_course];letmutq:VecDeque<usize>=VecDeque::new();letmutcount=0;// Initialize the graph & in degree vectorforpin&prerequisites{let(from,to)=(p[0],p[1]);graph[fromasusize].push(to);in_degree_vec[toasusize]+=1;}// Enqueue the first batch of nodes with in degree 0foriin0..num_course{ifin_degree_vec[i]==0{q.push_back(i);}}// Begin the traverse & update through the graphwhile!q.is_empty(){// Get the current node indexletindex=q.front().unwrap().clone();// This course can be finishedcount+=1;q.pop_front();foriin&graph[index]{// Update the in degree for the current nodein_degree_vec[*iasusize]-=1;// See if can be enqueuedifin_degree_vec[*iasusize]==0{q.push_back(*iasusize);}}}count==num_course}}