# C++ 16ms DFS with explanation

• This problem can be abstracted as a graph problem. A pair of prerequisite [u, v] can be considered as a directed edge v -> u.
It is feasible to crack this problem using Topological Sorting. And DFS method is straightforward.
Stack s records visited nodes in appropriate order. To detect cycle, in_path remembers all the visited nodes till the current node in the fly. If a node is already true in in_path, it means a cycle existing.

``````class Solution {
public:
vector<int> findOrder(int n, vector<pair<int, int>>& p) {
vector<int> res;
vector<vector<int>> edges (n, vector<int> ());
vector<bool> visited (n, false);
vector<bool> in_path (n, false);
stack<int> s;
for (auto & i : p) edges[i.second].push_back(i.first);
for (int i = 0; i < n; i++) {
if (!visited[i]) {
in_path[i] = true;
if (!DFS(i, n, edges, visited, s, in_path)) {
return res;
}
in_path[i] = false;
}
}
while (!s.empty()) {
res.push_back(s.top());
s.pop();
}
return res;
}
private:
// return false if there is a cycle
bool DFS (int u, int n, vector<vector<int>>& edges, vector<bool> & visited, stack<int>& s, vector<bool>& in_path) {
visited[u] = true;
for (int i = 0; i < edges[u].size(); i++) {
if (in_path[edges[u][i]] == true) return false;
in_path[edges[u][i]] = true;
if (!visited[edges[u][i]]) {
if (!DFS(edges[u][i], n, edges, visited, s, in_path)) return false;
}
in_path[edges[u][i]] = false;
}
s.push(u);
return true;
}
};
``````

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