原题链接：Leecode 207. 课程表

和这道题差不多：Leecode 802. 找到最终的安全状态 拓扑排序/DFS，这里的安全状态就是本题的无环的意思。


拓扑排序

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> degree(numCourses,0);
        vector<vector<int>> g(numCourses);
        queue<int> q;
        for(int i=0;i<prerequisites.size();i++)
        {
            int x=prerequisites[i][0];
            int y=prerequisites[i][1];
            g[y].push_back(x);
            degree[x]++;
        }
        for(int i=0;i<numCourses;i++)
        {
            if(!degree[i]) q.push(i);
        }
        int sum=0;
        while(!q.empty())
        {
            int cur=q.front();
            q.pop();
            for(auto x: g[cur])
            {
                degree[x]--;
                if(!degree[x]) q.push(x);
            }
            sum++;
        }
        return numCourses==sum;
    }
};

DFS

class Solution {
public:
    vector<int> v;
    vector<vector<int>> g;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        v.resize(numCourses);
        g.resize(numCourses);
        for(int i=0;i<prerequisites.size();i++)
        {
            int x=prerequisites[i][0];
            int y=prerequisites[i][1];
            g[x].push_back(y);
        }
        for(int i=0;i<numCourses;i++)
        {
            if(!v[i] && !dfs(g,i)) return false;
        }
        return true;
    }
    bool dfs(vector<vector<int>>& g,int i)
    {
        if(v[i]) return v[i]==2;
        v[i]=1;
        for(auto x: g[i])
        {
            if(!dfs(g,x)) return false;
        }
        v[i]=2;
        return true;
    }
};