# C++ clean topo sort solution

• The key point is to give 3 states to each course.
0 means a course isn't visited yet.
1 means a course is VISITED but it still waits for its prerequisites to finish, i.e, it's not finished.
2 means a course is finished.
So in each recursion, we first mark a course as 1, and try to finish all its prerequisites. If one of its prerequisites also has state 1, it means there's a cycle and we should stop going deeper by returning false. If all its prerequisites are finished, then we can finish the current course and mark it as 2 and put it into the order list. By doing these to each graph, we can get a valid course order.

``````    vector<int> findOrder(int n, vector<pair<int, int>>& pres) {
vector<vector<int>> edges(n);
for (auto pre : pres) {
edges[pre.first].push_back(pre.second);
}
vector<int> order;
vector<int> finished(n, 0);
for (int i = 0; i < n; ++i) {
if (!finish(i, edges, finished, order))
return vector<int>();
}
return order;
}

bool finish(int course, vector<vector<int>> &edges, vector<int> &finished, vector<int> &order) {
if (finished[course] == 1) return false;
if (finished[course] == 2) return true;
finished[course] = 1;
for (int i : edges[course]) {
if (!finish(i, edges, finished, order))
return false;
}
finished[course] = 2;
order.push_back(course);
return true;
}
``````

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