0
$\begingroup$

I have solved a problem that required me to find if the given directed graph had a cycle or not. The deal is, I used a recursive approach to solve it in the depth-first-search method. I was just wondering how the code would look in an Iterative approach of the same depth-first-search method. Here is my C++ code...

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites){
        // to make and adjacency list
        vector<int> adj[numCourses];
        for(auto x : prerequisites) adj[x[1]].push_back(x[0]);
        
        vector<bool> visited(numCourses, 0);
        vector<bool> dfsVisited(numCourses, 0);
        
        //iterating through all unvisited nodes
        for(int i = 0; i < numCourses; i++)
            if(!visited[i] and isCycle(i, visited, dfsVisited, adj))
                return 0;

        return 1;
    }

    bool isCycle(int node, vector<bool>& visited, vector<bool>& dfsVisited, vector<int> adj[]){
        if(dfsVisited[node]) return 1;
        if(visited[node]) return 0;

        dfsVisited[node] = 1;
        visited[node] = 1;

        for(int x : adj[node])
            if(isCycle(x, visited, dfsVisited, adj))
                return 1;
        dfsVisited[node] = 0;
        return 0;
    }
};

More specifically, when I use a stack, I am facing a problem in clearing the dfsVisited[node] while backtracking. Can someone please show me how an Iterative version of this code looks like? I will be grateful. Thank you

Improve this question
$\endgroup$
2
  • $\begingroup$ Coding questions are off-topic here. If you want to ask about an algorithm, please replace the code with concise pseudocode. If you want to ask about improving this code, that's off-topic here. $\endgroup$
    – D.W. ♦
    Commented Aug 18, 2021 at 21:09
  • $\begingroup$ That said, I think this is covered by other questions that ask how to convert recursion to iteration. $\endgroup$
    – D.W. ♦
    Commented Aug 18, 2021 at 21:10

0

Reset to default