返回

[Leetcode]210. Course Schedule II(C++)

题目描述

题目链接:210. Course Schedule II

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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

例子

例子 1

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

例子 2

Input:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output:[0,2,1,3] Explanation:There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

例子 3

Input:numCourses = 1, prerequisites = [] Output:[0]

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • All the pairs [ai, bi] are distinct.

解题思路

[Leetcode]207. Course Schedule(C++) 的进阶版,要求在判断是否能够上完所有课的基础上还要输出一个可行上课顺序,同样可以通过构建图并判断其中是否有环的方式来判断是否能上完所有的课,具体原理见上述链接。至于输出顺序,我们可以用一个栈来求解,首先从前置课出发进行遍历,对每一个后续课程进行判断,如果其中一门后续课中出现有环则直接返回空集,否则将当前课压入栈中。如此一来,最后栈中底部元素为最后上的课,顶部元素为前置课,依次输出到一个数组返回即可。有一种情况需要着重说明一下:假如有三门课 a b c 前置要求如下:

    1. a -> b
    1. b -> c
    1. a -> c

b 有前置要求 ac 有两个前置要求 ba。按照上述方式从 a 出发,有两种遍历方式(按照边在给定向量中的顺序不同都有可能出现):先判断 b 或者先判断 c。分别进行分析:

  • 先判断 b,入栈顺序为:

    • 判断c,压入:c 的后续课程,c
    • 判断其他后续课程,压入:b 的后续课程
    • b遍历完成,压入 b
    • 继续判断 a 的其他后续课程
    • 最后 bc的后面,满足要求
  • 先判断 c,入栈顺序为:

    • 判断c,压入:c 的后续课程,c
    • 中间可能会判断 a 的其他后续课程
    • 判断b,压入:b 的其他后续课程(由于c已经判断过了,不会重复添加),b
    • 继续判断 a 的其他后续课程
    • 最后 bc的后面,满足要求

尤其可以看出,在上述的情况下,无论先判断 b 还是 c都不会影响结果。

代码如下:

#include <stack>
#include <vector>

class Solution {
public:
    std::vector<int> findOrder(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[1]].push_back(preq[0]);
        }

        // std::vector<int> total_orders;
        std::stack<int> order;
        for (int i = 0; i < numCourses; ++i) {
            if (!dfs(hmap, status, i, order)) {
                return {};
            }
        }

        std::vector<int> ans;

        while (order.size()) {
            ans.push_back(order.top());
            order.pop();
        }

        return ans;
    }

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

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

GitHub 代码同步地址: 210.CourseScheduleIi.cpp

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

Built with Hugo
Theme Stack designed by Jimmy