Skip to content

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}|$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
enum class State { kInit, kVisiting, kVisited };

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

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

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

    return ranges::max(depth);
  }

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

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

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
enum State { kInit, kVisiting, kVisited }

class Solution {
  public int minimumSemesters(int n, int[][] relations) {
    List<Integer>[] graph = new List[n];
    State[] states = 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[] relation : relations) {
      final int u = relation[0] - 1;
      final int v = relation[1] - 1;
      graph[u].add(v);
    }

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

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

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

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

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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)]
    states = [State.kInit] * n
    depth = [1] * n

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

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

      states[u] = State.kVisiting
      for v in graph[u]:
        if hasCycle(v):
          return True
        depth[u] = max(depth[u], 1 + depth[v])
      states[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|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  int minimumSemesters(int n, vector<vector<int>>& relations) {
    vector<vector<int>> graph(n);
    vector<int> inDegrees(n);
    queue<int> q;

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

    // Perform topological sorting.
    for (int i = 0; i < n; ++i)
      if (inDegrees[i] == 0)
        q.push(i);

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  public int minimumSemesters(int n, int[][] relations) {
    List<Integer>[] graph = new List[n];
    int[] inDegrees = new int[n];

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def minimumSemesters(self, n: int, relations: list[list[int]]) -> int:
    graph = [[] for _ in range(n)]
    inDegrees = [0] * n

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

    # Perform topological sorting.
    q = collections.deque([i for i, d in enumerate(inDegrees) if d == 0])

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

    return step if n == 0 else -1