原题链接：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;
}
};
