1136. Parallel Courses

Approach 1: DFS

• Time: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{relations}|$
• Space: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{relations}|$

C++JavaPython

enum class State { kInit, kVisiting, kVisited };

class Solution {
 public:
  int minimumSemesters(int n, vector<vector<int>>& relations) {
    vector<vector<int>> graph(n);
    vector<State> state(n);
    vector<int> depth(n, 1);

    for (const vector<int>& r : relations)
      graph[r[0] - 1].push_back(r[1] - 1);

    for (int i = 0; i < n; ++i)
      if (hasCycle(graph, i, state, depth))
        return -1;

    return *max_element(begin(depth), end(depth));
  }

 private:
  bool hasCycle(const vector<vector<int>>& graph, int u, vector<State>& state,
                vector<int>& depth) {
    if (state[u] == State::kVisiting)
      return true;
    if (state[u] == State::kVisited)
      return false;

    state[u] = State::kVisiting;
    for (const int v : graph[u]) {
      if (hasCycle(graph, v, state, depth))
        return true;
      depth[u] = max(depth[u], 1 + depth[v]);
    }
    state[u] = State::kVisited;

    return false;
  }
};

enum State { kInit, kVisiting, kVisited }

class Solution {
  public int minimumSemesters(int n, int[][] relations) {
    List<Integer>[] graph = new List[n];
    State[] state = new State[n];
    int[] depth = new int[n];
    Arrays.fill(depth, 1);

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] r : relations)
      graph[r[0] - 1].add(r[1] - 1);

    for (int i = 0; i < n; ++i)
      if (hasCycle(graph, i, state, depth))
        return -1;

    return Arrays.stream(depth).max().getAsInt();
  }

  private boolean hasCycle(List<Integer>[] graph, int u, State[] state, int[] depth) {
    if (state[u] == State.kVisiting)
      return true;
    if (state[u] == State.kVisited)
      return false;

    state[u] = State.kVisiting;
    for (final int v : graph[u]) {
      if (hasCycle(graph, v, state, depth))
        return true;
      depth[u] = Math.max(depth[u], 1 + depth[v]);
    }
    state[u] = State.kVisited;

    return false;
  }
}

from enum import Enum


class State(Enum):
  kInit = 0
  kVisiting = 1
  kVisited = 2


class Solution:
  def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
    graph = [[] for _ in range(n)]
    state = [State.kInit] * n
    depth = [1] * n

    for u, v in relations:
      graph[u - 1].append(v - 1)

    def hasCycle(u: int) -> bool:
      if state[u] == State.kVisiting:
        return True
      if state[u] == State.kVisited:
        return False

      state[u] = State.kVisiting
      for v in graph[u]:
        if hasCycle(v):
          return True
        depth[u] = max(depth[u], 1 + depth[v])
      state[u] = State.kVisited

      return False

    if any(hasCycle(i) for i in range(n)):
      return -1
    return max(depth)

Approach 2: Topology

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$

C++JavaPython

class Solution {
 public:
  int minimumSemesters(int n, vector<vector<int>>& relations) {
    int ans = 0;
    vector<vector<int>> graph(n);
    vector<int> inDegree(n);
    queue<int> q;

    // Build graph
    for (const vector<int>& r : relations) {
      const int u = r[0] - 1;
      const int v = r[1] - 1;
      graph[u].push_back(v);
      ++inDegree[v];
    }

    // Topology
    for (int i = 0; i < n; ++i)
      if (inDegree[i] == 0)
        q.push(i);

    while (!q.empty()) {
      for (int sz = q.size(); sz > 0; --sz) {
        const int u = q.front();
        q.pop();
        --n;
        for (const int v : graph[u])
          if (--inDegree[v] == 0)
            q.push(v);
      }
      ++ans;
    }

    return n == 0 ? ans : -1;
  }
};

class Solution {
  public int minimumSemesters(int n, int[][] relations) {
    int ans = 0;
    List<Integer>[] graph = new List[n];
    int[] inDegree = new int[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    // Build graph
    for (int[] r : relations) {
      final int u = r[0] - 1;
      final int v = r[1] - 1;
      graph[u].add(v);
      ++inDegree[v];
    }

    // Topology
    Queue<Integer> q = IntStream.range(0, n)
                           .filter(i -> inDegree[i] == 0)
                           .boxed()
                           .collect(Collectors.toCollection(ArrayDeque::new));

    while (!q.isEmpty()) {
      for (int sz = q.size(); sz > 0; --sz) {
        final int u = q.poll();
        --n;
        for (final int v : graph[u])
          if (--inDegree[v] == 0)
            q.offer(v);
      }
      ++ans;
    }

    return n == 0 ? ans : -1;
  }
}

class Solution:
  def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
    ans = 0
    graph = [[] for _ in range(n)]
    inDegree = [0] * n

    # Build graph
    for a, b in relations:
      u = a - 1
      v = b - 1
      graph[u].append(v)
      inDegree[v] += 1

    # Topology
    q = collections.deque([i for i, d in enumerate(inDegree) if d == 0])

    while q:
      for _ in range(len(q)):
        u = q.popleft()
        n -= 1
        for v in graph[u]:
          inDegree[v] -= 1
          if inDegree[v] == 0:
            q.append(v)
      ans += 1

    return ans if n == 0 else -1