golang 解法, 执行用时: 28 ms, 内存消耗: 6.7 MB, 提交时间: 2023-10-22 10:48:23

func minimumSemesters(n int, relations [][]int) int {
    graph := make([][]int, n+1) //邻接表
    for i:=0; i<n; i++ {
        graph[i] = []int{}
    }
    indegree := make([]int, n+1) //入度表
    for i:=0; i<len(relations); i++ { //构建邻接表和入度表
        first, second := relations[i][0], relations[i][1]
        graph[first] = append(graph[first], second)
        indegree[second]++
    }
    var queue []int
    for i:=1; i<n; i++ { //入度为0的点写入队列
        if 0 == indegree[i] {
            queue = append(queue, i)
        }
    }

    ans := 0
    visit := 0 //课程访问数量
    for 0 != len(queue) {
        ans++ //入度同时为0的节点在一个学期内一起修
        size := len(queue)
        for i:=0; i<size; i++ { //将同一批入度为0的节点修完
            cur := queue[i]
            for _, nxt := range graph[cur] {
                indegree[nxt]--
                if 0 == indegree[nxt] { //入度为0，写入队列，为下一批修的课程
                    queue = append(queue, nxt)
                }
            }
            visit++
        }
        queue = queue[size:]
    }

    if visit != n { //如果课程访问数量 != 课程数，肯定存在环
        return -1
    }
    return ans
}

python3 解法, 执行用时: 68 ms, 内存消耗: 20.5 MB, 提交时间: 2023-10-22 10:48:02

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        graph = {i: [] for i in range(1, N + 1)}
        for start_node, end_node in relations:
            graph[start_node].append(end_node)

        visited = {}

        def dfs(node: int) -> int:
            # 返回最长路（含）
            if node in visited:
                return visited[node]
            else:
                # 标记为正在访问
                visited[node] = -1

            max_length = 1
            for end_node in graph[node]:
                length = dfs(end_node)
                # 我们遇到了一个环！
                if length == -1:
                    return -1
                else:
                    max_length = max(length+1, max_length)
            # 标记为已经访问过
            visited[node] = max_length
            return max_length

        max_length = -1
        for node in graph.keys():
            length = dfs(node)
            # 我们遇到了一个环！
            if length == -1:
                return -1
            else:
                max_length = max(length, max_length)
        return max_length

python3 解法, 执行用时: 76 ms, 内存消耗: 20.6 MB, 提交时间: 2023-10-22 10:47:45

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        graph = {i: [] for i in range(1, N + 1)}
        for start_node, end_node in relations:
            graph[start_node].append(end_node)

        # 检查图中是否有环
        visited = {}

        def dfs_check_cycle(node: int) -> bool:
            # return True if graph has a cycle
            if node in visited:
                return visited[node]
            else:
                # 标记为正在访问
                visited[node] = -1
            for end_node in graph[node]:
                if dfs_check_cycle(end_node):
                    # 我们遇到了一个环！
                    return True
            # 标记为已经访问过
            visited[node] = False
            return False

        # if has cycle, return -1
        for node in graph.keys():
            if dfs_check_cycle(node):
                return -1

        # 如果没有环，返回最长路
        visited_length = {}

        def dfs_max_path(node: int) -> int:
            # 返回最长路（含）
            if node in visited_length:
                return visited_length[node]
            max_length = 1
            for end_node in graph[node]:
                length = dfs_max_path(end_node)
                max_length = max(length+1, max_length)
            # 储存
            visited_length[node] = max_length
            return max_length

        return max(dfs_max_path(node)for node in graph.keys())

python3 解法, 执行用时: 68 ms, 内存消耗: 18.4 MB, 提交时间: 2023-10-22 10:47:28

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        graph = {i: [] for i in range(1, N + 1)}
        in_count = {i: 0 for i in range(1, N + 1)}  # 或者入度
        for start_node, end_node in relations:
            graph[start_node].append(end_node)
            in_count[end_node] += 1

        queue = []
        # 我们使用 list 因为我们
        # 在这份代码中不会弹出前面的元素
        for node in graph:
            if in_count[node] == 0:
                queue.append(node)

        step = 0
        studied_count = 0
        # 开始使用BFS学习
        while queue:
            # 开始一个新学期
            step += 1
            next_queue = []
            for node in queue:
                studied_count += 1
                end_nodes = graph[node]
                for end_node in end_nodes:
                    in_count[end_node] -= 1
                    # 如果所有先修课程都已经学习
                    if in_count[end_node] == 0:
                        next_queue.append(end_node)
            queue = next_queue

        return step if studied_count == N else -1

cpp 解法, 执行用时: 56 ms, 内存消耗: 26.3 MB, 提交时间: 2023-10-22 10:47:15

class Solution {
public:
   int minimumSemesters(int N, vector<vector<int>>& relations) {
       vector<int> inCount(N + 1, 0);  // 或者入度
       vector<vector<int>> graph(N + 1);
       for (auto& relation : relations) {
           graph[relation[0]].push_back(relation[1]);
           inCount[relation[1]]++;
       }
       int step = 0;
       int studiedCount = 0;
       vector<int> bfsQueue;
       for (int node = 1; node < N + 1; node++) {
           if (inCount[node] == 0) {
               bfsQueue.push_back(node);
           }
       }
       // 开始使用 BFS 学习
       while (!bfsQueue.empty()) {
           // 开始一个新学期
           step++;
           vector<int> nextQueue;
           for (auto& node : bfsQueue) {
               studiedCount++;
               for (auto& endNode : graph[node]) {
                   inCount[endNode]--;
                   // 如果所有先修课程都已经学习
                   if (inCount[endNode] == 0) {
                       nextQueue.push_back(endNode);
                   }
               }
           }
           bfsQueue = nextQueue;
       }

       // 检查是否学习所有课程
       return studiedCount == N ? step : -1;
   }
};

java 解法, 执行用时: 6 ms, 内存消耗: 43.8 MB, 提交时间: 2023-10-22 10:47:02

class Solution {
   public int minimumSemesters(int N, int[][] relations) {
       int[] inCount = new int[N + 1]; // 或者入度
       List<List<Integer>> graph = new ArrayList<>(N + 1);
       for (int i = 0; i < N + 1; ++i) {
           graph.add(new ArrayList<Integer>());
       }
       for (int[] relation : relations) {
           graph.get(relation[0]).add(relation[1]);
           inCount[relation[1]]++;
       }
       int step = 0;
       int studiedCount = 0;
       List<Integer> bfsQueue = new ArrayList<>();
       for (int node = 1; node < N + 1; node++) {
           if (inCount[node] == 0) {
               bfsQueue.add(node);
           }
       }
       // 开始使用 BFS 学习
       while (!bfsQueue.isEmpty()) {
           // 开始一个新学期
           step++;
           List<Integer> nextQueue = new ArrayList<>();
           for (int node : bfsQueue) {
               studiedCount++;
               for (int endNode : graph.get(node)) {
                   inCount[endNode]--;
                   // 如果所有先修课程都已经学习
                   if (inCount[endNode] == 0) {
                       nextQueue.add(endNode);
                   }
               }
           }
           bfsQueue = nextQueue;
       }

       // 检查是否学习所有课程
       return studiedCount == N ? step : -1;
   }
}