Topological Sorting

Topological Sorting is an ordering of the vertices of a graph such that if a vertex precedes a vertex in the ordering then there does not exist any path from vertex to vertex .
Obviously, this sort of ordering is never possible in a graph which has a directed cycle. And hence, top-sort (a popular abbreviation) can not be done in an undirected graph (since, every edge is actually a directed cycle between its 2 endpoints). So, top-sort is only applicable to Directed Acyclic Graphs (DAGs).
The Algorithm
The most important observation which leads to the algorithm here is:-
Any vertex with in-degree can precede any other vertex in the graph.(*)
This is simply because, no vertex can have a path to a vertex with in-degree .
This means, we can safely add any vertex with in-degree as the next vertex in our ordering and delete it from the graph and repeat the same procedure till the graph becomes empty.
One can note that to check if a vertex is removed, one might just check if its in-degree is 0 or not.
Hence, if we represent the graph in the standard adjacency list, the C++ implementation will be like:
vector<int> topSort() {
queue<int> Q;
for(int i=1; i<=n; i++) {
if(inDegree[i] == 0) {
Q.push(i);
}
}
vector<int> res;
while(not Q.empty()) {
int now = Q.front();
res.push_back(now);
for(int next: graph[now]) {
if(inDegree[next] > 0) {
inDegree[next]--;
if(inDegree[next] == 0) {
Q.push(next);
}
}
}
}
return res;
}
Complexity and Correctness
Correctness follows directly from the observation (*). In the above implementation, for each vertex, we keep on deleting all the edges coming out from that vertex in time per edge. Hence, the complexity is simply . Since, in-degrees can be calculated while constructing the graph, its also and hence the overall complexity is also .