## 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 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.

## 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;
}
``````
Copy The Code &

Input

cmd
numCourses = 2, prerequisites = [[1,0]]

Output

cmd
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;
}
};
``````
Copy The Code &

Input

cmd
numCourses = 2, prerequisites = [[1,0]]

Output

cmd
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) {
}
}
while (!queue.isEmpty()) {
int removed = queue.remove();
for (Integer dependentCourse : map.getOrDefault(removed, new HashSet < >())) {
indegree[dependentCourse]--;
if (indegree[dependentCourse] == 0) {
}
}
}
return taken.size() == numCourses;
}
}
``````
Copy The Code &

Input

cmd
numCourses = 2, prerequisites = [[1,0],[0,1]]

Output

cmd
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]
for (const e of graph[cur] || []) {
indegree[e]--
if (indegree[e] === 0 && !set.has(e)) {
nxt.push(e)
}
}
}

q = nxt
}

return set.size === numCourses
}
``````
Copy The Code &

Input

cmd
numCourses = 2, prerequisites = [[1,0],[0,1]]

Output

cmd
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
``````
Copy The Code &

Input

cmd
numCourses = 2, prerequisites = [[1,0]]

Output

cmd
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];

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 (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)
}
}
}
``````
Copy The Code &

Input

cmd
numCourses = 2, prerequisites = [[1,0]]

Output

cmd
numCourses = 2, prerequisites = [[1,0]]