Clean and Easy-to-understand C++ Code Using DFS


  • 0
    P

    This is a very typical application of DFS or topological sort. When you reach a parent node while traversing a child path, there is a cycle, and the courses cannot be finished.

    class Solution {
    public:
        vector<vector<int>> adj;
        vector<char> visited;
        enum {
            UNVISITED = 0,
            VISITING = 1,
            VISITED = 2
        };
        
        bool hasCycle(int root) {
            visited[root] = VISITING;
            for(int child: adj[root]) {
                if(visited[child] == VISITING)
                    return true;
                if(visited[child] == UNVISITED && hasCycle(child))
                    return true;
            }
            visited[root] = VISITED;
            return false;
        }
    
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            // build the adjacency list
            adj.clear();
            adj.resize(numCourses);
            for(auto& p : prerequisites) {
                int course = p.first;
                int dependency = p.second;
                adj[dependency].push_back(course);
            }
            visited.clear();
            visited.resize(numCourses);
            // perform DFS to detect cycles
            for(int course = 0; course < numCourses; ++course) {
                if(visited[course] == UNVISITED) {
                    if(hasCycle(course))
                        return false;
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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