课程表

1. 题目描述

picture 0

样例输入 #1

输入：numCourses = 2, prerequisites = [[1,0]]

样例输出 #1

输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

2. 分析

我们可以将深度优先搜索的流程与拓扑排序的求解联系起来, 用一个栈来存储所有已经搜索完成的节 点。对于一个节点w, 如果它的所有相邻节点都已经搜索完成, 那么在搜索回溯到 u 的时候, 本身也会变成一个已经搜索完成的节点。这里 的「相邻节点」指的是从 u 出发通过一条有向边可以到达的所有节点。假设我们当前搜索到了节点 u, 如果它的所有相邻节点都已经搜索完成, 那么这些节点都已经在栈中了, 此时我们就可以把 u 入栈。可以发现, 如果我们从栈顶往栈底的顺序看,由于 u 处于栈顶的位置, 那么 u 出现在所有 u 的相邻节点的前面。因此对于 u 这个节点而言, 它是满足拓扑排序的要求的。这样以来, 我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候, 我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

3. 代码

 #include <vector>
#include <iostream>
using namespace std;
class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;
public:
    void dfs(int u) {
        visited[u] = 1;
        for (int v : edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info : prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return valid;
    }
};
// 示例用法
int main() {
    Solution solution;
    int numCourses = 4;
    vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
    bool canOrder = solution.canFinish(numCourses, prerequisites);
    if (canOrder) {
        cout << "可以完成所有课程。" << endl;
    } else {
        cout << "无法完成所有课程，存在环。" << endl;
    }
    return 0;
}