C++ clean code for DFS solution with simple comments


  • 0
    L
    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.
    }

Log in to reply
 

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