class Solution {
public:
bool canFinish(int n, vector<vector<int>>& pre) {
if(pre.empty()||pre[0].empty()) return true;
vector<vector<bool>> g(n,vector<bool>(n,false));
for(auto q:pre)
g[q[0]][q[1]]=true;
vector<int> st(n,false);
//0表示未进入递归,1表示可以修读,2表示不能修读
for(int i=0;i<n;i++)
{
if(!st[i]&&!dfs(i,st,n,g))
return false;
else if(st[i]==2) return false;
}
return true;
}
bool dfs(int num,vector<int>& st,int n,vector<vector<bool>> &g)//尝试修第num门课
{
st[num]=2;
for(int i=0;i<n;i++)
if(g[num][i])//遍历所有先修课程
{
if(i==num)//如果先修课程包含自己,直接返回false
{
st[num]=2;
return false;
}
if(!st[i]&&!dfs(i,st,n,g))
return false;
else if(st[i]==2)
return false;
}
st[num]=1;
return true;
}
};
LeetCode 207. 课程表
发布时间 2023-07-09 11:53:48作者: 穿过雾的阴霾