# DFS C++ solution topological sort

• ``````class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
if (numCourses == 0) return vector<int>(0, 0);
vector<int> startList(numCourses, 0);
for (auto pre : prerequisites) {
startList[pre.second]++;
}

int visitedNodes = 0;
vector<int> marks(numCourses, 0); // 0 indicates not marked, 1 temporary marked, 2 permanent marked
vector<int> orders;
while (visitedNodes < numCourses) {
//find one unvisited node with indegree == 0
int startNode = findOneUnvisitedNode(numCourses, startList, marks);
// if cannot find a startNode, return false;
if (startNode >= numCourses) return vector<int>(0, 0);
// dfs from start node
if (!dfs(startNode, adjacentList, marks, visitedNodes, orders)) return vector<int>(0, 0);
}
return orders;
}

int findOneUnvisitedNode(int numCourses, vector<int>& startList, vector<int>& marks) {
int startNode = 0;
for (; startNode < numCourses; startNode++) {
if (startList[startNode] == 0 && marks[startNode] == 0)
break;
}
return startNode;
}

bool dfs (int startNode, unordered_map<int, vector<int> >& adjacentList, vector<int>& marks, int & visitedNodes, vector<int>& orders) {
if (marks[startNode] == 1) return false;
if (marks[startNode] == 0) {
marks[startNode] = 1;