README.md

1136. 并行课程

English Version

题目描述

给你一个整数 n ，表示编号从 1 到 n 的 n 门课程。另给你一个数组 relations ，其中 relations[i] = [prevCoursei, nextCoursei] ，表示课程 prevCoursei 和课程 nextCoursei 之间存在先修关系：课程 prevCoursei 必须在 nextCoursei 之前修读完成。

在一个学期内，你可以学习 任意数量 的课程，但前提是你已经在上一学期修读完待学习课程的所有先修课程。

请你返回学完全部课程所需的 最少 学期数。如果没有办法做到学完全部这些课程的话，就返回 -1。

 

 

示例 1：

输入：n = 3, relations = [[1,3],[2,3]]
输出：2
解释：上图表示课程之间的关系图：
在第一学期，可以修读课程 1 和 2 。
在第二学期，可以修读课程 3 。

示例 2：

输入：n = 3, relations = [[1,2],[2,3],[3,1]]
输出：-1
解释：没有课程可以学习，因为它们互为先修课程。

 

提示：

• 1 <= n <= 5000
• 1 <= relations.length <= 5000
• relations[i].length == 2
• 1 <= prevCoursei, nextCoursei <= n
• prevCoursei != nextCoursei
• 所有 [prevCoursei, nextCoursei] 互不相同

解法

方法一：拓扑排序

Python3

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
            for _ in range(len(q)):
                i = q.popleft()
                n -= 1
                for j in g[i]:
                    indeg[j] -= 1
                    if indeg[j] == 0:
                        q.append(j)
        return -1 if n else ans

Java

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<>();
        }
        int[] indeg = new int[n];
        for (int[] r : relations) {
            int a = r[0] - 1, b = r[1] - 1;
            g[a].add(b);
            ++indeg[b];
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            if (indeg[i] == 0) {
                q.offer(i);
            }
        }
        int ans = 0;
        while (!q.isEmpty()) {
            ++ans;
            for (int k = q.size(); k > 0; --k) {
                int i = q.poll();
                --n;
                for (int j : g[i]) {
                    if (--indeg[j] == 0) {
                        q.offer(j);
                    }
                }
            }
        }
        return n == 0 ? ans : -1;
    }
}

C++

class Solution {
public:
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        vector<vector<int>> g(n);
        vector<int> indeg(n);
        for (auto& r : relations) {
            int a = r[0] - 1, b = r[1] - 1;
            g[a].push_back(b);
            ++indeg[b];
        }
        queue<int> q;
        for (int i = 0; i < n; ++i)
            if (indeg[i] == 0) q.push(i);
        int ans = 0;
        while (!q.empty()) {
            ++ans;
            for (int k = q.size(); k; --k) {
                int i = q.front();
                q.pop();
                --n;
                for (int j : g[i])
                    if (--indeg[j] == 0) q.push(j);
            }
        }
        return n == 0 ? ans : -1;
    }
};

Go

func minimumSemesters(n int, relations [][]int) int {
	g := make([][]int, n)
	indeg := make([]int, n)
	for _, r := range relations {
		a, b := r[0]-1, r[1]-1
		g[a] = append(g[a], b)
		indeg[b]++
	}
	q := []int{}
	for i, v := range indeg {
		if v == 0 {
			q = append(q, i)
		}
	}
	ans := 0
	for len(q) > 0 {
		ans++
		for k := len(q); k > 0; k-- {
			i := q[0]
			q = q[1:]
			n--
			for _, j := range g[i] {
				indeg[j]--
				if indeg[j] == 0 {
					q = append(q, j)
				}
			}
		}
	}
	if n == 0 {
		return ans
	}
	return -1
}

...