C++ clean code for DFS solution with simple comments

• ``````bool canFinish(int numCourses, vector<pair<int, int>>& prer) {
vector<vector<int>> gragh(numCourses);
vector<int> visited(numCourses, 0); // White at initialization
for (int i = 0; i < prer.size(); i++) {
gragh[prer[i].second].push_back(prer[i].first);
}
bool cycle = false;
for (int i = 0; i < numCourses; i++) {
if (cycle) return false;
if (visited[i] == 0) dfs_top(i, gragh, visited, cycle);
}
return !cycle;
}
void dfs_top(int node, vector<vector<int>> &gragh, vector<int> &visited, bool &cycle) {
if (visited[node] == 1) {cycle = true; return;} // cycle occurs, break the dfs chain and all return
visited[node] = 1; //Gray, searching
for (int i = 0; i < gragh[node].size(); i++) {
dfs_top(gragh[node][i], gragh, visited, cycle);
if (cycle) return; // do some pruning here
}
visited[node] = 2; //Black Once finished.
}``````

• Consider this test case: numCourses is large, and the prerequisite dependency is like 0->1->2->3->4->.....->(n-1). IMO, the call stack will become too deep and cause issue.

• You are right. The algorithm can be changed as:

``````class Solution{
vector<vector<int>> vec;
vector<int> visited;
bool cycle;
public:
bool canFinish(int numCourses,vector<pair<int,int>> &prer){

vector<int> vec2;
for(int i=0;i<numCourses;i++){
vec.push_back(vec2);
visited.push_back(0);
}
for(int i=0;i<prer.size();i++)
// vec[prer[i].second].push_back(prer[i].first);
vec[prer[i].first].push_back(prer[i].second);

cycle=0;

for(int i=0;i<numCourses;i++){
if(visited[i]==2)continue;
else if(visited[i]==1)return false;
// if(visited[i]==0)
dfs_fun(i);
if(cycle==1)return false;
}
return true;
}

void dfs_fun(int i){
if(visited[i]==1){cycle=1;return;}
visited[i]=1;

for(int j=0;j<vec[i].size();j++){
int node=vec[i][j];
if(visited[node]==0)
dfs_fun(node);
else if(visited[node]==1){cycle=1;return;}
else if(visited[node]==2)continue;
if(cycle)return;//
}
visited[i]=2;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.