My C++ Dfs with Cycle check algorithm.


  • 7
    J

    It would be easier if consider the course and it's require as a DAG,
    eg, [0, 1] is vetex 0 have a edge to 1, and the course the job is check whether this DAG has a cycle.

    it can be easy archive by DFS,
    the key idea of DFS checking cycle is check if the calling vetex already in the stack, if it was in stack, it indeed is a cycle.

    Please reference Algorithms 4th, Page 576.

    Below is my code,
    two parts, 1 part is setup the graph, and another part is use dfs checking if there is cycle.

    class Solution {
    public:
    using vi = vector<int>;
            
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vi> adj(numCourses, vi());
            for (auto p : prerequisites) {
                adj[p.first].push_back(p.second);
            }
            
            bool hasCycle = false;
            
            vector<bool> onStack(numCourses, false);
            vector<bool> visited(numCourses, false);
            for(int i = 0; i < adj.size(); i++) {
                if (!visited[i])
                    dfs(i, adj, hasCycle, onStack, visited);
            }
            return !hasCycle;
        }
        
        void dfs(int v, vector<vi> &adj, bool &hasCycle, vector<bool> &onStack, vector<bool> &visited) {
         
            visited[v] = true;
            onStack[v] = true;
            
            for (auto &w : adj[v]) {
                if (hasCycle)
                    return;
                else if (!visited[w]) {
                    dfs(w, adj, hasCycle, onStack, visited);
                } else if (onStack[w]) {
                    hasCycle = true;
                    return;
                }
            }
            
            onStack[v] = false;
        }
    };

  • 0
    M

    if (hasCycle)
    return;

    Is this condition necessary.


Log in to reply
 

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