can any one tell why my can finish funciton is giving false for the "course schedule " 1 problem?
i added various cout statements to debug it but still can’t find the error.
My approach is if the graph is a dag, then we will have a topological sort which will mean that we can complete the courses.
Problem LInk : - LeetCode
Code:
class Solution {
public:
bool checkCycle(vector<vector<int>> &graph,vector<bool> &visited,vector<bool> &dfsVisited,int src)
{
visited[src]=true;
dfsVisited[src]=true;
for(auto it : graph[src])
{
if(!visited[it]){
if(checkCycle(graph,visited,dfsVisited,it))
{
cout<<"First return statement inside checkcycle"<<endl;
return true;
}
}
else if(dfsVisited[it])
{
cout<<"Second return statement inside checkCycle"<<endl;
return true;
}
}
dfsVisited[src]=false;
cout<<"third return statement inside checkCycle"<<endl;
return false;
}
bool canFinish(int n, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(n+1,vector<int> ());
for(int i=0;i<prerequisites.size(); i++){
int v=prerequisites[i][0];
int u=prerequisites[i][1];
graph[u].push_back(v);
}
vector<bool> visited(n,false);
vector<bool> dfsVisited(n,false);
for(int i=0;i<n;i++)
{
if(!visited[i])
{
if(checkCycle(graph,visited,dfsVisited,i)==true);
{
cout<<"First return statement inside canFinish"<<endl;
return false;
}
}
}
cout<<"second return statement inside canFinish"<<endl;
return true;
}
};