Why does this DFS-based topological sort algorithm work?

Question

Here is the algorithm that I pulled from this competitive programming resource.

int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
    reverse(ans.begin(), ans.end());
}

How does this algorithm avoid adding vertices to the topologically sorted collection that have incoming directed edges? Say, for example, that the first vertex (0 in this example) checked by the for loop has an incoming directed edge from vertex (1). What is stopping this algorithm from outputting (0) before first ensuring that (1) has been output?

Answer 1

It's building the output vector backwards. If there's an incoming directed edge from vertex (1) to vertex (0), you want to output (0) before (1).

Note that dfs(int v) calls ans.push_back(v) only after it recurses to all its descendants. This ensures that anything that follows v will have been added to the output vector before v. Anything not visited[] after dfs(0) returns is either unrelated to 0 or its descendants (and therefore can be added later), or precedes them (and therefore should be added later).