Topological Sort
Topological sorting arranges the vertices of a directed graph so that every directed edge points forward in the resulting order.
For an edge , vertex must appear before vertex . We can think of as a task that depends on : before we can process , we must first complete .
In the previous lecture, we learned how to detect a cycle in a directed graph. If a directed cycle exists, topological sorting is impossible because every vertex in the cycle depends, directly or indirectly, on itself. In this lecture, we assume that this check has already been performed and that the graph is a DAG.
A DAG is a directed graph that contains no directed cycles. Our goal is now to construct one valid topological order of its vertices.
You are given a directed acyclic graph with vertices and edges. Output any ordering of all vertices such that, for every edge , vertex appears before vertex .
Consider the following edges:
One valid order is: .
Another valid order is: .
Both orders are correct. Vertices and do not depend on each other, so either of them may appear first. A topological order is not always unique. We only need to find one valid order.
Suppose the graph contains an edge . Before DFS can finish processing , the vertex must already be completely processed:
Therefore, if we append each vertex only when its DFS call finishes, then is placed into the finishing list before .
This is the reverse of the order we need. The edge requires to appear before , but the finishing list contains before . Therefore, after all DFS calls finish, we reverse the entire list.
We must not append a vertex when DFS first enters it.
At that moment, some vertices reachable through its outgoing edges may still be unprocessed. Placing the vertex into the answer immediately could put it after a vertex that depends on it.
Instead, we append the vertex only after every outgoing edge has been handled. For a vertex :
At this moment, every vertex reached directly from has already been placed into the finishing list.
For every edge , vertex is appended to the finishing list before vertex . Therefore, after reversing the finishing list, vertex appears before vertex .
We keep an array and a vector .
Algorithm:
The input graph is guaranteed to be a DAG.
1. Process one DFS component.
1.1. Mark the current vertex as visited.
1.2. Inspect every outgoing neighbor of the current vertex.
1.3. If the neighbor is not visited, continue DFS from that neighbor.
1.4. After all outgoing neighbors are processed, append the current vertex to order.
2. Build the topological order.
2.1. Visit every vertex from 1 through n.
2.2. Start DFS from every vertex that is still unvisited.
2.3. Reverse order after all DFS calls are complete.
2.4. Output the reversed order.
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
int m;
bool used[N];
vector<int> g[N];
vector<int> order;
void dfs(int v) {
used[v] = true;
for (int u : g[v]) {
if (!used[u]) {
dfs(u);
}
}
order.push_back(v);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int v;
int u;
cin >> v >> u;
g[v].push_back(u);
}
for (int v = 1; v <= n; v++) {
if (!used[v]) {
dfs(v);
}
}
reverse(order.begin(), order.end());
for (int v : order) {
cout << v << ' ';
}
cout << '\n';
return 0;
}