1136.Parallel-Courses

1136. Parallel Courses

题目地址

https://leetcode.com/problems/parallel-courses/

题目描述

There are N courses, labelled from 1 to N.

We are given relations[i] = [X, Y], representing a prerequisite relationship between course X and course Y: course X has to be studied before course Y.

In one semester you can study any number of courses as long as you have studied all the prerequisites for the course you are studying.

Return the minimum number of semesters needed to study all courses.  If there is no way to study all the courses, return -1.

Example 1:
Input: N = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: 
In the first semester, courses 1 and 2 are studied. In the second semester, course 3 is studied.

Example 2:
Input: N = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: 
No course can be studied because they depend on each other.

Note:
1 <= N <= 5000
1 <= relations.length <= 5000
relations[i][0] != relations[i][1]
There are no repeated relations in the input.

代码

Approach #1 Topological Sort + BFS

Time: O(1) && Space: O(1)

class Solution {
  public int minimumSemesters(int N, int[][] relations) {
        Map<Integer, List<Integer>> g = new HashMap<>();
    int[] inDegree = new int[N+1];
    for (int[] r: relations) {
      g.computeIfAbsent(r[0], l -> new ArrayList<>()).add(r[1]);
      ++inDegree[r[1]];
    }
    Queue<Integer> g = new LinkedList<>();
    for (int i = 1; i <= N; i++) {
      if (inDegree[i] == 0) {
        q.offer(i);
      }
    }
    int semester = 0;
    while (!q.isEmpty()) {
      for (int sz = q.size(); sz > 0; sz--) {
        int c = q.poll();
        --N;
        if (!g.containsKey(c)) {
          continue;
        }
        for (int course: g.remove(c)) {        // c's in-degree is currently 0, but it has no prerequsite
          if (--inDegree[course] == 0) {        // decrease the in-degree of course's neighbors
            q.offer(course);        // add current 0 in-degree vertex into Queue
          }
        }
      }
      ++semester;        // need one more semester
    }
    return N == 0 ? semester : -1;
  }
}

Approach #2 DFS + Longest Path Length

class Solution {
  private int maxPathLength = Integer.MIN_VALUE;
  private boolean hasCycle = false;
  public int minimumSemesters(int n, int[][] relations) {
    HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();
    for (int[] relation: relations) {
      graph.putIfAbsent(relation[0], new LinkedList<>());
      graph.get(relation[0]).add(relation[1]);
    }

    int[] depth = new int[N+1];
    boolean[] color = new boolean[N+1];
    for (int i = 1; i <= N; i++) {
      dfs(i, color, depth, graph);
    } 
    return hasCycle ? -1 : maxPathLength;
  }

  private int dfs(int root, boolean[] color, int[] depth, HashMap<Integer, LinkedList<Integer>> graph) {
    if (color[root])        hasCycle = true;
    if (depth[root] > 0 || hasCycle)        return depth[root];
    color[root] = true;
    int max = 0;
    // Find the longest path from the neighbor courses
    if (graph.containsKey(root)) {
      for (int neighbor: graph.get(root)) {
        max = Math.max(max, dfs(neighbor, color, depth, graph));
      }
    }
    color[root] = false;
    depth[root] = max + 1;
    maxPathLength = Math.max(maxPathLength, depth[root]);
    return depth[root];
  }
}