跳到主要内容

Course Schedule

描述​

TODO

分析​

TODO

代码​

BFS​

// Course Schedule
// Time complexity: O(E+V)
// Space complexity: O(E+V)
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>()); // adjacent list
        vector<int> in(numCourses); // in degree
        for (auto p : prerequisites) {
            graph[p[1]].push_back(p[0]);
            ++in[p[0]];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (auto neighbor : graph[t]) {
                --in[neighbor];
                if (in[neighbor] == 0) q.push(neighbor);
            }
        }
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] != 0) return false;
        }
        return true;
    }
};

DFS​

// Course Schedule
// Time complexity: O(E+V)
// Space complexity: O(E+V)
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>()); // // adjacent list
        vector<int> visited(numCourses); // 0, not visited; 1, visited; -1, cyclic
        for (auto p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        for (int i = 0; i < numCourses; ++i) {
            if (!canFinishDFS(graph, visited, i)) return false;
        }
        return true;
    }
    bool canFinishDFS(vector<vector<int>>& graph, vector<int>& visited, int i) {
        if (visited[i] == -1) return false;
        if (visited[i] == 1) return true;
        visited[i] = -1;
        for (auto neighbor : graph[i]) {
            if (!canFinishDFS(graph, visited, neighbor)) return false;
        }
        visited[i] = 1;
        return true;
    }
};

相关题目​