207. Course schedule

207_solution1_dfs.c

#include <stdbool.h>
#include <stdlib.h>

// adjacency in CSR form: node u's neighbors are edges[start[u] .. start[u+1])
static bool dfs(const int *start, const int *edges, int *state, int node) {
  if (state[node] == 1)
    return false; // back on the current path: cycle
  if (state[node] == 2)
    return true; // already fully explored

  state[node] = 1;
  for (int e = start[node]; e < start[node + 1]; e++)
    if (!dfs(start, edges, state, edges[e]))
      return false;
  state[node] = 2;
  return true;
}

bool canFinish(int numCourses, int **prerequisites, int prerequisitesSize,
               int *prerequisitesColSize) {
  (void)prerequisitesColSize; // always 2

  int *start = calloc(numCourses + 1, sizeof(int));
  int *edges = malloc((prerequisitesSize ? prerequisitesSize : 1) * sizeof(int));
  for (int i = 0; i < prerequisitesSize; i++)
    start[prerequisites[i][0] + 1]++;
  for (int u = 0; u < numCourses; u++)
    start[u + 1] += start[u];
  int *fill = malloc(numCourses * sizeof(int));
  for (int u = 0; u < numCourses; u++)
    fill[u] = start[u];
  for (int i = 0; i < prerequisitesSize; i++)
    edges[fill[prerequisites[i][0]]++] = prerequisites[i][1];
  free(fill);

  int *state = calloc(numCourses, sizeof(int)); // 0 = unvisited, 1 = on path, 2 = done
  bool ok = true;
  for (int i = 0; i < numCourses && ok; i++)
    ok = dfs(start, edges, state, i);

  free(start);
  free(edges);
  free(state);
  return ok;
}

207_solution2_bfs.c

#include <stdbool.h>
#include <stdlib.h>

bool canFinish(int numCourses, int **prerequisites, int prerequisitesSize,
               int *prerequisitesColSize) {
  (void)prerequisitesColSize; // always 2

  // unlocks in CSR form: course b's dependents are edges[start[b] .. start[b+1])
  int *start = calloc(numCourses + 1, sizeof(int));
  int *edges = malloc((prerequisitesSize ? prerequisitesSize : 1) * sizeof(int));
  int *remaining = calloc(numCourses, sizeof(int)); // prerequisites still missing
  for (int i = 0; i < prerequisitesSize; i++) {
    start[prerequisites[i][1] + 1]++;
    remaining[prerequisites[i][0]]++;
  }
  for (int u = 0; u < numCourses; u++)
    start[u + 1] += start[u];
  int *fill = malloc(numCourses * sizeof(int));
  for (int u = 0; u < numCourses; u++)
    fill[u] = start[u];
  for (int i = 0; i < prerequisitesSize; i++)
    edges[fill[prerequisites[i][1]]++] = prerequisites[i][0];
  free(fill);

  int *queue = malloc(numCourses * sizeof(int));
  int head = 0, tail = 0;
  for (int c = 0; c < numCourses; c++)
    if (remaining[c] == 0)
      queue[tail++] = c;

  while (head < tail) {
    int c = queue[head++];
    for (int e = start[c]; e < start[c + 1]; e++)
      if (--remaining[edges[e]] == 0)
        queue[tail++] = edges[e];
  }

  free(start);
  free(edges);
  free(remaining);
  free(queue);
  return tail == numCourses;
}

207_solution1_dfs.cpp

#include <vector>

using namespace std;

class Solution {
public:
  bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
    vector<vector<int>> adjacency(numCourses);
    for (const auto &p : prerequisites)
      adjacency[p[0]].push_back(p[1]);

    vector<int> state(numCourses, 0); // 0 = unvisited, 1 = on path, 2 = done
    for (int i = 0; i < numCourses; i++)
      if (!dfs(adjacency, state, i))
        return false;
    return true;
  }

private:
  bool dfs(const vector<vector<int>> &adjacency, vector<int> &state, int node) {
    if (state[node] == 1)
      return false; // back on the current path: cycle
    if (state[node] == 2)
      return true; // already fully explored

    state[node] = 1;
    for (int next : adjacency[node])
      if (!dfs(adjacency, state, next))
        return false;
    state[node] = 2;
    return true;
  }
};

207_solution2_bfs.cpp

#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
  bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
    vector<vector<int>> unlocks(numCourses); // b -> courses that need b
    vector<int> remaining(numCourses, 0);    // prerequisites still missing

    for (auto &p : prerequisites) {
      int a = p[0], b = p[1];
      unlocks[b].push_back(a);
      remaining[a]++;
    }

    queue<int> q;
    for (int c = 0; c < numCourses; c++)
      if (remaining[c] == 0)
        q.push(c);

    int taken = 0;
    while (!q.empty()) {
      int c = q.front();
      q.pop();
      taken++;

      for (int next : unlocks[c])
        if (--remaining[next] == 0)
          q.push(next);
    }

    return taken == numCourses;
  }
};

207_solution1_dfs.go

package graphs

func canFinish(numCourses int, prerequisites [][]int) bool {
    adjacency := make([][]int, numCourses)
    for _, p := range prerequisites {
        adjacency[p[0]] = append(adjacency[p[0]], p[1])
    }

    state := make([]int, numCourses) // 0 = unvisited, 1 = on path, 2 = done

    var dfs func(node int) bool
    dfs = func(node int) bool {
        if state[node] == 1 {
            return false // back on the current path: cycle
        }
        if state[node] == 2 {
            return true // already fully explored
        }

        state[node] = 1
        for _, next := range adjacency[node] {
            if !dfs(next) {
                return false
            }
        }
        state[node] = 2
        return true
    }

    for i := 0; i < numCourses; i++ {
        if !dfs(i) {
            return false
        }
    }
    return true
}

207_solution2_bfs.go

package graphs

func canFinish(numCourses int, prerequisites [][]int) bool {
    unlocks := make([][]int, numCourses) // b -> courses that need b
    remaining := make([]int, numCourses) // prerequisites still missing

    for _, p := range prerequisites {
        a, b := p[0], p[1]
        unlocks[b] = append(unlocks[b], a)
        remaining[a]++
    }

    queue := []int{}
    for c := 0; c < numCourses; c++ {
        if remaining[c] == 0 {
            queue = append(queue, c)
        }
    }

    taken := 0
    for len(queue) > 0 {
        c := queue[0]
        queue = queue[1:]
        taken++

        for _, next := range unlocks[c] {
            remaining[next]--
            if remaining[next] == 0 {
                queue = append(queue, next)
            }
        }
    }

    return taken == numCourses
}

207_solution1_dfs.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        for (int[] p : prerequisites)
            adjacency.get(p[0]).add(p[1]);

        int[] state = new int[numCourses]; // 0 = unvisited, 1 = on path, 2 = done
        for (int i = 0; i < numCourses; i++)
            if (!dfs(adjacency, state, i))
                return false;
        return true;
    }

    private boolean dfs(List<List<Integer>> adjacency, int[] state, int node) {
        if (state[node] == 1)
            return false; // back on the current path: cycle
        if (state[node] == 2)
            return true; // already fully explored

        state[node] = 1;
        for (int next : adjacency.get(node))
            if (!dfs(adjacency, state, next))
                return false;
        state[node] = 2;
        return true;
    }
}

207_solution2_bfs.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>(numCourses); // b -> courses that need b
        for (int i = 0; i < numCourses; i++)
            unlocks.add(new ArrayList<>());
        int[] remaining = new int[numCourses]; // prerequisites still missing

        for (int[] p : prerequisites) {
            int a = p[0], b = p[1];
            unlocks.get(b).add(a);
            remaining[a]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int c = 0; c < numCourses; c++)
            if (remaining[c] == 0)
                q.add(c);

        int taken = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            taken++;

            for (int next : unlocks.get(c))
                if (--remaining[next] == 0)
                    q.add(next);
        }

        return taken == numCourses;
    }
}

207_solution1_dfs.js

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const adjacency = Array.from({ length: numCourses }, () => []);
  for (const [course, pre] of prerequisites) adjacency[course].push(pre);

  const state = new Array(numCourses).fill(0); // 0 = unvisited, 1 = on path, 2 = done

  const dfs = (node) => {
    if (state[node] === 1) return false; // back on the current path: cycle
    if (state[node] === 2) return true; // already fully explored

    state[node] = 1;
    for (const next of adjacency[node]) if (!dfs(next)) return false;
    state[node] = 2;
    return true;
  };

  for (let i = 0; i < numCourses; i++) if (!dfs(i)) return false;
  return true;
};

207_solution2_bfs.js

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const unlocks = Array.from({ length: numCourses }, () => []); // b -> courses that need b
  const remaining = new Array(numCourses).fill(0); // prerequisites still missing

  for (const [a, b] of prerequisites) {
    unlocks[b].push(a);
    remaining[a]++;
  }

  const queue = [];
  for (let c = 0; c < numCourses; c++) if (remaining[c] === 0) queue.push(c);

  let taken = 0;
  for (let head = 0; head < queue.length; head++) {
    taken++;
    for (const next of unlocks[queue[head]]) if (--remaining[next] === 0) queue.push(next);
  }

  return taken === numCourses;
};

207_solution1_dfs.py

from typing import List


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adjacency: List[List[int]] = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            adjacency[course].append(pre)

        state = [0] * numCourses  # 0 = unvisited, 1 = on path, 2 = done

        def dfs(node: int) -> bool:
            if state[node] == 1:
                return False  # back on the current path: cycle
            if state[node] == 2:
                return True  # already fully explored

            state[node] = 1
            for nxt in adjacency[node]:
                if not dfs(nxt):
                    return False
            state[node] = 2
            return True

        return all(dfs(i) for i in range(numCourses))

207_solution2_bfs.py

from collections import deque
from typing import List


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        unlocks: List[List[int]] = [[] for _ in range(numCourses)]  # b -> courses that need b
        remaining = [0] * numCourses  # prerequisites still missing

        for a, b in prerequisites:
            unlocks[b].append(a)
            remaining[a] += 1

        q = deque(c for c in range(numCourses) if remaining[c] == 0)

        taken = 0
        while q:
            c = q.popleft()
            taken += 1

            for nxt in unlocks[c]:
                remaining[nxt] -= 1
                if remaining[nxt] == 0:
                    q.append(nxt)

        return taken == numCourses

207_solution1_dfs.rs

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut adjacency = vec![Vec::new(); n];
        for p in &prerequisites {
            adjacency[p[0] as usize].push(p[1] as usize);
        }

        let mut state = vec![0u8; n]; // 0 = unvisited, 1 = on path, 2 = done
        (0..n).all(|i| Self::dfs(&adjacency, &mut state, i))
    }

    fn dfs(adjacency: &[Vec<usize>], state: &mut [u8], node: usize) -> bool {
        if state[node] == 1 {
            return false; // back on the current path: cycle
        }
        if state[node] == 2 {
            return true; // already fully explored
        }

        state[node] = 1;
        for &next in &adjacency[node] {
            if !Self::dfs(adjacency, state, next) {
                return false;
            }
        }
        state[node] = 2;
        true
    }
}

207_solution2_bfs.rs

use std::collections::VecDeque;

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut unlocks = vec![Vec::new(); n]; // b -> courses that need b
        let mut remaining = vec![0; n]; // prerequisites still missing

        for p in &prerequisites {
            let (a, b) = (p[0] as usize, p[1] as usize);
            unlocks[b].push(a);
            remaining[a] += 1;
        }

        let mut q: VecDeque<usize> = (0..n).filter(|&c| remaining[c] == 0).collect();

        let mut taken = 0;
        while let Some(c) = q.pop_front() {
            taken += 1;

            for &next in &unlocks[c] {
                remaining[next] -= 1;
                if remaining[next] == 0 {
                    q.push_back(next);
                }
            }
        }

        taken == n
    }
}