408算法题leetcode--第19天

207. 课程表

• 207. 课程表
• 思路：bfs和dfs都行，看注释
• 时间和空间：O(n + m)

class Solution {
private:
    vector<vector<int>>graph;  // 邻接矩阵
    vector<int>in;  // 入度
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 拓扑排序, bfs
        // 如果节点入度 = 0，入队
        // 循环：移出节点的出边，如果相邻点入读为0，也入队
        // 2种情况：1. 入队了n个节点，则true；否则是有环图，false
        // 也可以用dfs，用flag数组标记，如果某个点遍历2次，则false，其他为true
        graph.resize(numCourses);
        in.resize(numCourses);
        for(auto& i : prerequisites){
            graph[i[1]].push_back(i[0]);  // 1 -> 0
            ++in[i[0]];
        }
        // 队列，找入队为0的点
        queue<int>q;
        for(int i = 0; i < numCourses; i++){
            if(in[i] == 0){
                q.push(i);
            }
        }
        // 循环
        int count = 0;
        while(!q.empty()){
            ++count;
            int temp = q.front();
            q.pop();
            // 删除出边
            for(int it : graph[temp]){
                --in[it];
                if(in[it] == 0){
                    q.push(it);
                }
            }
        }
        return count == numCourses;
    }
};

210. 课程表 II

• 210. 课程表 II
• 思路，空间和时间同上

class Solution {
private:
    vector<vector<int>>graph;
    vector<int>in;
    vector<int>ret;
    
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // bfs
        // 找入度为0的节点
        graph.resize(numCourses);
        in.resize(numCourses);
        for(auto it : prerequisites){
            graph[it[1]].push_back(it[0]);
            ++in[it[0]];
        }
        queue<int>q;
        for(int i = 0; i < numCourses; i++){
            if(in[i] == 0){
                q.push(i);
            }
        }
        // 循环
        while(!q.empty()){
            int temp = q.front();
            q.pop();
            ret.push_back(temp);
            // 删除入边
            for(auto it : graph[temp]){
                --in[it];
                if(in[it] == 0){
                    q.push(it);
                }
            }
        }
        if(ret.size() != numCourses) return vector<int>{};
        return ret; 
    }
};