[LeetCode 207] 课程表

207. 课程表

本质上是判断图中是否有环

1.dfs

参考

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
  public:
    // 1：从当前结点开始的拓扑是无环的/已完成访问
    // 0：还未遍历过
    //-1：正在遍历
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        vector<int> visit(numCourses, 0); //标志
        vector<vector<int>> tmp(numCourses);
        if (prerequisites.empty())
            return true;
        for (int i = 0; i < prerequisites.size(); i++) {
            //这样写也可以，但是相当于把图中所有的箭头都反过来了，该有环还是有环
            //正常写应该是tmp[prerequisites[i][1]].push_back(prerequisites[i][0]); 意思是该门课是哪些课的先修课
            tmp[prerequisites[i][0]].push_back(prerequisites[i][1]); //对于该课程来说需要修的课
        }
        bool ans = true;
        for (int i = 0; i < numCourses; i++) {
            if (!ans)
                break;
            ans = ans && dfs(i, visit, tmp);
        }
        return ans;
    }
    bool dfs(int i, vector<int> &visit, vector<vector<int>> &tmp) {
        if (visit[i] == -1) //回路.有环
            return false;

        if (visit[i] == 1)
            return true; //可以确定从该结点出发没有回路

        //第一次访问
        visit[i] = -1; //正在访问
        for (int j = 0; j < tmp[i].size(); j++) {
            if (dfs(tmp[i][j], visit, tmp))
                continue; //这个地方没有回路
            return false;
        }
        visit[i] = 1; //该结点出去的每一个结点都访问完了，没有回路
        return true;
    }
};

int main() {
    vector<vector<int>> prerequisites = {{1, 3}, {2, 0}, {1, 2}, {0, 1}};
    Solution s;
    bool res = s.canFinish(4, prerequisites);
    cout << res;

    return 0;
}

2.bfs：拓扑排序

参考
这个就比dfs慢多了，复杂度应该是

class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            //拓扑排序
            vector<int>inDegree(numCourses);
            int num=0;

            for(int i=0; i<prerequisites.size(); i++)
                inDegree[prerequisites[i][0]]++;

            queue<int>q;
            for(int i=0; i<numCourses; i++) {
                if(inDegree[i]==0) {
                    q.push(i);
                    num++;
                }
            }
            while(!q.empty()) {
                int cur=q.front();
                q.pop();
                for(int i=0; i<prerequisites.size(); i++) {
                    // 以cur为入的结点
                    if(prerequisites[i][1]==cur)
                        inDegree[prerequisites[i][0]]--;
                    else continue;
                    if(inDegree[prerequisites[i][0]]==0) {
                        q.push(prerequisites[i][0]);
                        num++;
                    }
                }
            }
            return num==numCourses;
        }
};