# Simple AC C++ DFS toposort solution

• ``````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;
}
};``````

• It still works if we delete these codes:

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

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