Easy understanding DFS solution in C++

  • 1
    class Solution {
        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;
            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.