Topological sorting on a graph seems like an immensely powerful operation:
No matter whether the algorithm ends in success or failure, we obtain an important information about the topology of the graph, i.e. whether it is cyclic or not.
If it ends in failure, we can trivially find the cycle that let the algorithm end in failure, and if it succeeds, we get a working linear ordering on the graph.
And all that is possible in asymptotic linear time!
(It's in $\mathcal O (n+m)$; $n,m$ are the vertices and edges of the graph)
While I've seen the proofs and algorithms, and yes, it works, it still baffles me how exactly this is possible.
Looking at another way, a topological sorting a combination of all partial orders of the graph into a single linear order, which still maintains all the original partial orders. So e.g. even if we're given a set of partial orders, we'd still turn it into a graph, and probably be faster than any alternative.
Why exactly is topological sorting so fast?
I think I've found an answer that suffices for me.
Generally, I'd say the complexity of an algorithm derives from the diversity of possible inputs and the structure properties (constraints) that you have to take care of.
Graphs are insanely diverse, the range of problems they can be applied to alone shows this. And then, a graph has quite a lot of structure as well. So, unless you can somehow abuse its structure, I'd think problems on graphs would be fairly difficult.
However, for the algorithm, we can use the structure property that every acyclic graph has a node with no incoming edges. So, instead of having to care about the whole graph, we just have to observe it locally. As therefore the topology of the graph as whole turns irrelevant, the diversity of graphs (that we care about) greatly diminishes as well, and thus we achieve such a high time efficiency.
I guess what had put me off so much was that the statement that makes all this possible is so simple (and easy to deduce).