Algorithm
Problem Name: 207. Course Schedule
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 course0you 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 <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCourses- All the pairs prerequisites[i] are unique.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int has_cycle(int *buff, int n, int sz, int *visited) {
int i, *node;
if (visited[n] == -1) return 0;
if (visited[n] == 1) return 1;
visited[n] = 1;
node = &buff[n * sz];
for (i = 0; i < sz; i ++) {
if (node[i] != 0 && has_cycle(buff, node[i], sz, visited)) {
return true;
}
}
visited[n] = -1;
return false;
}
bool canFinish(int numCourses, int** prerequisites, int prerequisitesRowSize, int prerequisitesColSize) {
int ret = true;
int *buff, *root, *node;
int i, a, b;
int *visited;
buff = calloc((numCourses + 1) * numCourses, sizeof(int)); // each node with all possible neighbors
visited = calloc((numCourses + 1), sizeof(int));
//assert(buff && visited);
root = &buff[0]; // root node has neighbors of all
for (i = 0; i < numCourses; i ++) {
root[i] = i + 1;
}
for (i = 0; i < prerequisitesRowSize; i ++) {
a = prerequisites[i][1] + 1;
b = prerequisites[i][0];
node = &buff[a * numCourses];
node[b] = b + 1;
}
if (has_cycle(buff, 0, numCourses, visited)) {
ret = false;
}
free(buff);
free(visited);
return ret;
}
Input
numCourses = 2, prerequisites = [[1,0]]
Output
true
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int>indegree(numCourses);
vector < vector<int>>graph(numCourses);
for(auto p: prerequisites){
graph[p.second].push_back(p.first);
indegree[p.first]++;
}
for(int i = 0; i < numCourses; i++){
int j = 0;
for(; j < numCourses; j++) if(indegree[j] == 0) break;
if(j == numCourses) return false;
indegree[j] = -1;
for(auto x: graph[j]) indegree[x]--;
}
return true;
}
};
Input
numCourses = 2, prerequisites = [[1,0]]
Output
true
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map();
int[] indegree = new int[numCourses];
for (int[] prerequisite : prerequisites) {
map.computeIfAbsent(prerequisite[1], k -> new HashSet < >()).add(prerequisite[0]);
indegree[prerequisite[0]]++;
}
Queue < Integer> queue = new LinkedList<>();
Set taken = new HashSet<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.add(i);
taken.add(i);
}
}
while (!queue.isEmpty()) {
int removed = queue.remove();
for (Integer dependentCourse : map.getOrDefault(removed, new HashSet < >())) {
indegree[dependentCourse]--;
if (indegree[dependentCourse] == 0) {
taken.add(dependentCourse);
queue.add(dependentCourse);
}
}
}
return taken.size() == numCourses;
}
}
Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const canFinish = function (numCourses, prerequisites) {
const set = new Set()
const indegree = Array(numCourses).fill(0)
const graph = {}
for (const [s, e] of prerequisites) {
indegree[e]++
if (graph[s] == null) graph[s] = []
graph[s].push(e)
}
let q = []
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) q.push(i)
}
while (q.length) {
const nxt = []
for (let i = 0, size = q.length; i < size; i++) {
const cur = q[i]
set.add(cur)
for (const e of graph[cur] || []) {
indegree[e]--
if (indegree[e] === 0 && !set.has(e)) {
nxt.push(e)
}
}
}
q = nxt
}
return set.size === numCourses
}
Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def canFinish(self, numCourses, prerequisites):
def cycle(course):
visited[course] = 0
for Next in route[course]:
if visited[Next] == 0 or (visited[Next] == -1 and cycle(Next)): return True
visited[course] = 1
return False
route, visited = {i: [] for i in range(numCourses)}, [-1] * numCourses
for req in prerequisites: route[req[1]].append(req[0])
for course in range(numCourses):
if visited[course] == -1 and cycle(course): return False
return True
Input
numCourses = 2, prerequisites = [[1,0]]
Output
numCourses = 2, prerequisites = [[1,0]]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0207_CourseSchedule
{
public bool CanFinish(int numCourses, int[][] prerequisites)
{
var adj = new bool[numCourses, numCourses];
BuildGraph(adj, prerequisites);
var visited = new int[numCourses];
for (int i = 0; i < numCourses; i++)
if (visited[i] == 0 && !DFS(adj, visited, i, numCourses)) return false;
return true;
}
private bool DFS(bool[,] adj, int[] visited, int i, int numCourses)
{
visited[i] = 1;
for (int j = 0; j < numCourses; j++)
{
if (adj[i, j])
{
if (visited[j] == 1) return false;
if (visited[j] == 0)
if (!DFS(adj, visited, j, numCourses)) return false;
}
}
visited[i] = 2;
return true;
}
private void BuildGraph(bool[,] adj, int[][] prerequisites)
{
foreach (var prerequisite in prerequisites)
adj[prerequisite[1], prerequisite[0]] = true;
}
}
}
Input
numCourses = 2, prerequisites = [[1,0]]
Output
numCourses = 2, prerequisites = [[1,0]]