Parallel Courses

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #topologicalsort, #bfs

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// https://code.dennyzhang.com/parallel-courses // Basic Ideas: topologicalsort + bfs // // Design algorithm: // Build degrees for each nodes // BFS starts with 0 degrees // // When queue is empty, it stops // If we haven't visited all nodes, the graph has circles // Complexity: Time O(v+e), Space O(v+e) func minimumSemesters(N int, relations [][]int) int { // there are no duplicate edges edges := make([][]int, N) // 1->3, 1->2 for i, _ := range edges { edges[i] = []int{} } indegrees := make([]int, N) for _, edge := range relations { n1, n2 := edge[0]-1, edge[1]-1 edges[n1] = append(edges[n1], n2) indegrees[n2]++ } level := 0 queue := []int{} for i, v := range indegrees { if v == 0 { queue = append(queue, i) } } for len(queue)>0 { nexts := []int{} for _, n1 := range queue { for _, n2 := range edges[n1] { indegrees[n2]-- if indegrees[n2] == 0 { nexts = append(nexts, n2) } } } queue = nexts level++ } // check whether there are nodes not visited for _, v := range indegrees { if v != 0 { return -1 } } return level }