Easy understanding DFS solution in C++


  • 1
    R
    class Solution {
    public:
        bool dfs_get_courses_list(vector<vector<int>> &matrix, vector<int> &visited, int idx, vector<int> &ret)
        {
            if (visited[idx] == -1) return false;
            if (visited[idx] == 1)  return true;
            
            visited[idx] = -1;
            
            for (auto it : matrix[idx])
            {
                if (!dfs_get_courses_list(matrix, visited, it, ret))
                    return false;
            }
            ret.push_back(idx);
            visited[idx] = 1;
            return true;
        }
    
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) 
        {
            vector<int> visited(numCourses, 0);
            vector<int> ret;
    
            vector<vector<int>> matrix(numCourses);
            for (int i=0; i<prerequisites.size(); ++i)
                matrix[prerequisites[i].second].push_back(prerequisites[i].first); // build directed graph
            
            for (int i=0; i<numCourses; ++i)
            {
                if (!dfs_get_courses_list(matrix, visited, i, ret))
                {
                    vector<int> fret;
                    return fret;
                }
            }
            
            reverse(ret.begin(), ret.end());
            
            return ret;
        }
    };

Log in to reply
 

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