Question

Formatted question description: https://leetcode.ca/all/1136.html

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

Algorithm

Solution 1. Greedy Algorithm with BFS.

Since we can take as many courses as we want, taking all courses that do not have outstanding prerequisites each semester must be one valid answer that gives a minimum number of semesters needed.

Construct a directed graph and in degree of each node(course).
Add all courses that do not have any prerequisites(in degree == 0) to a queue.
BFS on all neighboring nodes(courses) of the starting courses and decrease their indegrees by 1. If a neighboring course’s indegree becomes 0, it means all its prerequisites are met, add it to queue as this course can be taken in the next semester.
After all neighboring nodes of the courses that are taken in the current semester have been visited, increment semester count by 1. Repeat until the queue is empty.
When doing the BFS, keep a count of courses taken, compare this count with the total number of courses to determine if it is possible to study all courses.

Both the runtime and space are O(V+E).

Solution 2. DFS with Dynamic Programming

Because we have to first take all prerequisites of a course beforing taking it, we know the following two property of this problem.

If there is a cycle, there is no way of studying all courses.
If there is no cycle, the minimum number of semesters needed to study all courses is determined by the longest acyclic path, i.e, we are looking for the longest acyclic path with each edge’s weight being 1. This is exactly the same problem with Max path value in directed graph. The only difference is the dynamic programming state.

Both runtime and space are O(V+E).

Code

Java

public class Parallel_Courses {

    class Solution_BFS {
        public int minimumSemesters(int N, int[][] relations) {

            // 1.  Construct a directed graph and in degree of each node(course).
            Map<Integer, Set<Integer>> graph = new HashMap<>(); // course => its next courses
            int[] inDegree = new int[N + 1];

            for(int[] edge : relations) {
                graph.getOrDefault(edge[0], new HashSet<>()).add(edge[1]);
                inDegree[edge[1]]++;
            }

            // 2. Add all courses that do not have any prerequisites(in degree == 0) to a queue.
            Queue<Integer> q = new LinkedList<>();
            int semester = 0, courseCount = 0;
            for(int i = 1; i <= N; i++) {
                if(inDegree[i] == 0) {
                    q.add(i);
                }
            }

            // 3. BFS on all neighboring nodes(courses)
            while(q.size() > 0) {
                int size = q.size();
                courseCount += size;
                for(int i = 0; i < size; i++) {
                    int curr = q.poll();
                    for(int neighbor : graph.get(curr)) {
                        inDegree[neighbor]--;
                        if(inDegree[neighbor] == 0) {
                            q.add(neighbor);
                        }
                    }
                }
                semester++; // every bfs layer, +1
            }
            return courseCount == N ? semester : -1;
        }
    }

    // Related: [Daily Coding Problem 72] Max path value in directed graph
    class Solution_DFS {

        private final int UNVISITED = 0;
        private final int VISITING = 1;
        private final int VISITED = 2;
        private int[] longestPath;
        private int[] states;

        // If there is no cycle, the minimum number of semesters needed to study all courses is determined by the longest acyclic path,
        // i.e, we are looking for the longest acyclic path with each edge's weight being 1.
        public int minimumSemesters(int N, int[][] relations) {

            Map<Integer, Set<Integer>> graph = constructGraph(N, relations);
            longestPath = new int[N + 1];
            states = new int[N + 1];

            for(int course = 1; course <= N; course++) {
                if(states[course] == UNVISITED) {
                    if(dfs(graph, course)) {
                        return -1;
                    }
                }
            }
            int ans = 0;
            for(int course = 1; course <= N; course++) {
                ans = Math.max(ans, longestPath[course]);
            }
            return ans;
        }

        private Map<Integer, Set<Integer>> constructGraph(int N, int[][] relations) {
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            for(int i = 1; i <= N; i++) {
                graph.put(i, new HashSet<>());
            }
            for(int i = 0 ; i < relations.length; i++) {
                graph.get(relations[i][0]).add(relations[i][1]);
            }
            return graph;
        }

        // true if any cycle. false if no cycle
        private boolean dfs(Map<Integer, Set<Integer>> graph, int course) {
            if(states[course] == VISITED) {
                return false;
            } else if(states[course] == VISITING) { // cycle found
                return true;
            }
            states[course] = VISITING;
            for(int neighbor : graph.get(course)) {
                if(dfs(graph, neighbor)) {
                    return true;
                }
            }
            for(int neighbor : graph.get(course)) {
                longestPath[course] = Math.max(longestPath[course], longestPath[neighbor]);
            }
            longestPath[course]++;
            states[course] = VISITED;
            return false;
        }
    }

}

// OJ: https://leetcode.com/problems/parallel-courses/
// Time: O(N + E)
// Space: O(N + E)
class Solution {
public:
    int minimumSemesters(int n, vector<vector<int>>& E) {
        vector<vector<int>> G(n);
        vector<int> indegree(n);
        for (auto &e : E) {
            int u = e[0] - 1, v = e[1] - 1;
            G[u].push_back(v);
            indegree[v]++;
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (indegree[i] == 0) q.push(i);
        }
        int step = 0, seen = 0;
        while (q.size()) {
            int cnt = q.size();
            seen += cnt;
            while (cnt--) {
                int u = q.front();
                q.pop();
                for (int v : G[u]) {
                    if (--indegree[v] == 0) q.push(v);
                }
            }
            ++step;
        }
        return seen == n ? step : -1;
    }
};

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        g = defaultdict(list)
        indeg = [0] * n
        for a, b in relations:
            g[a - 1].append(b - 1)
            indeg[b - 1] += 1
        ans = 0
        q = deque([i for i, v in enumerate(indeg) if v == 0])
        while q:
            ans += 1 # every bfs layer, +1
            for _ in range(len(q)):
                i = q.popleft()
                n -= 1 # one course finished
                for j in g[i]:
                    indeg[j] -= 1
                    if indeg[j] == 0:
                        q.append(j)
        return -1 if n else ans

1136 - Parallel Courses

Question

Algorithm

Solution 1. Greedy Algorithm with BFS.

Solution 2. DFS with Dynamic Programming

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Solution 1. Greedy Algorithm with BFS.

Solution 2. DFS with Dynamic Programming

Code

All Problems

All Solutions