Let us have two components, A and B. We traverse A first and then move on to B such that, while visiting B, we find an edge B → A (remember that we have already traversed A).

So whatever component we traverse after A must appear before A in the final output — like B, A — so that if we get an edge B → A, it satisfies the rules of topological sorting.

But in an array, we can only insert efficiently at the end (inserting at the front is costly). So we just keep inserting at the end, getting something like A, B, but knowing we’ll reverse it later to become B, A.

However, that final reversal would also flip the internal order of each component (A and B). To preserve that, we write each component already reversed — that is, we record nodes while backtracking.

So when the global reversal happens, we get B, A, where both B and A keep their correct internal ordering. That’s the beauty of DFS-based topological sorting: each component is built bottom-up so that one simple reversal fixes everything.

void swap(int* A, int* B) {

if (A == B) return;

*A = *A ^ *B;
*B = *A ^ *B;
*A = *A ^ *B;
}

void DFS(size_t i, vector<vector<int>>& graph, vector<int>& vis, vector<int>& solution) {

size_t m = graph.size(), n = graph[i].size();

vis[i] = 1;

for (size_t j = 0; j < n; j++) {

int node = graph[i][j];

if (!vis[node]) {
DFS(node, graph, vis, solution);
}

}

solution.push_back(i);
}

vector<int> topologicalsort(vector<vector<int>>& graph) {

size_t m = graph.size();

vector<int> vis(m, 0);
vector<int> solution;

for (size_t i = 0; i < m; i++) {

if (!vis[i]) {
DFS(i, graph, vis, solution);
}
}

size_t lt = 0, rt = solution.size() - 1;

while(lt < rt) {

swap(solution + lt, solution + rt);
++lt, --rt;
}

return solution;
}