207. 課程表

本質(zhì)上是判斷圖中是否有環(huán)

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：從當前結(jié)點開始的拓撲是無環(huán)的/已完成訪問
    // 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++) {
            //這樣寫也可以，但是相當于把圖中所有的箭頭都反過來了，該有環(huán)還是有環(huán)
            //正常寫應該是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) //回路.有環(huán)
            return false;

        if (visit[i] == 1)
            return true; //可以確定從該結(jié)點出發(fā)沒有回路

        //第一次訪問
        visit[i] = -1; //正在訪問
        for (int j = 0; j < tmp[i].size(); j++) {
            if (dfs(tmp[i][j], visit, tmp))
                continue; //這個地方?jīng)]有回路
            return false;
        }
        visit[i] = 1; //該結(jié)點出去的每一個結(jié)點都訪問完了，沒有回路
        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為入的結(jié)點
                    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;
        }
};