# C++ DFS topological sort solution.

• class Solution {
public:

``````vector<int> findOrder(int numCourses, vector<pair<int, int> > & prerequisites) {
// use dfs topological sort
vector<int> ans;
if (numCourses == 0) return ans;
if (numCourses == 1) return vector<int>(1,0);

// preprocess the graph into a non-duplicate edge list
vector<vector<int> > edge(numCourses, vector<int>());
vector<set<int> > uedge(numCourses, set<int>());
for(auto pre : prerequisites){
uedge[pre.first].insert(pre.second);
}
for(int i=0; i<numCourses; ++i){
edge[i].insert(edge[i].end(), uedge[i].begin(), uedge[i].end());
}
uedge.clear();

// do a graph depth first search topological sort
vector<bool> vis(numCourses, false);// visited means the node has been explored
stack<int> dfs_s, path;
unordered_set<int> on_path;
for (int i=0; i<numCourses; ++i){
if (vis[i]) continue;
dfs_s.push(i);
while(!dfs_s.empty()){
int cur = dfs_s.top();
vis[cur] = true;
path.push(cur);
on_path.insert(cur);
int ct = 0;
for(auto e : edge[cur]){
if (on_path.find(e) != on_path.end()){
return vector<int>(); // this is a path with cycle
}
if (vis[e]) continue;
dfs_s.push(e);
++ct;
}
if (ct == 0){// end of current path
while (!path.empty() && path.top() == dfs_s.top()){
int t = path.top();
ans.push_back(t);
on_path.erase(t);
path.pop();
dfs_s.pop();
}
}
}
}
return ans;
}
``````

};

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