返回

[Leetcode]207. Course Schedule(C++)

题目描述

题目链接:207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

例子

例子 1

Input:numCourses = 2, prerequisites = [[1,0]] Output:true Explanation:There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

例子 2

Input:numCourses = 2, prerequisites = [[1,0],[0,1]] Output:false Explanation:There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints

  • 1 <= numCourses <= 10^5
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

解题思路

课与课之间的前置关系可以组成一个或多个树,其中每一条边都是单向边(由当前课指向前置课程),我们要做的是检查树中是否存在环,如果存在则表示出现循环依赖,因此没办法上完所有课。检查是否有环的方法是拓扑排序,如下所示:

#include <vector>

class Solution {
public:
    bool canFinish(int numCourses,
                   std::vector<std::vector<int>>& prerequisites) {
        std::vector<std::vector<int>> hmap(numCourses);
        std::vector<int> status(numCourses, 0);
        for (auto preq : prerequisites) {
            hmap[preq[0]].push_back(preq[1]);
        }

        for (int i = 0; i < numCourses; ++i) {
            if (!dfs(hmap, status, i)) {
                return false;
            }
        }

        return true;
    }

private:
    bool dfs(const std::vector<std::vector<int>>& hmap,
             std::vector<int>& status, int current_course) {
        for (int preq : hmap[current_course]) {
            if (status[preq] == 1) {
                continue;
            } else if (status[preq] == -1) {
                return false;
            } else {
                status[preq] = -1;
                if (!dfs(hmap, status, preq)) {
                    return false;
                }
                status[preq] = 1;
            }
        }

        return true;
    }
};
  • 时间复杂度: O(|E|)
  • 空间复杂度: O(max(|E|, |V|))

GitHub 代码同步地址: 207.CourseSchedule.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy