Simple AC C++ DFS toposort solution


  • 6
    Y
    class Solution {
        vector<bool> visited;
        vector<int> path; 
        vector<bool> rec;
        vector<list<int>> graph;
        
    public:
    
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) 
        {
            vector<int> cycle();
            
            if(prerequisites.empty())
            {
                for(int i = 0; i < numCourses; ++i)
                {
                    path.push_back(i);
                }
                return path;
            }
            
            graph.assign(numCourses, list<int>());
            visited.assign(numCourses, false);
            rec.assign(numCourses, false);
            
            for(int i = 0; i < prerequisites.size(); ++i)
            {
                graph[prerequisites[i].first].push_back(prerequisites[i].second);
            }
            
            for(int i = 0; i < graph.size(); ++i)
            {
                if(visited[i]) continue;
                if(isCycle(i)) return vector<int>();
            }
            
            return path;
        }
    
        bool isCycle(int course)
        {
            visited[course] = true;
            rec[course] = true;
            
            for(auto it = graph[course].begin(); it!=graph[course].end(); ++it)
            {
                if(!visited[*it])
                {
                    if(isCycle(*it)) return true;
                }
                if(rec[*it]) return true;
            }
            rec[course] = false;
            path.push_back(course);
            return false;
        }
    };

  • 0
    G

    It still works if we delete these codes:

       if(prerequisites.empty())
            {
                for(int i = 0; i < numCourses; ++i)
                {
                    path.push_back(i);
                }
                return path;
            }

Log in to reply
 

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