Topological sort in linear time?

Question

I read a few places which claim that its possible to do topological sort in linear time. One such claim is made here - They say - O(V+E) http://en.wikipedia.org/wiki/Topological_sorting

But the algo they have : has a for each inside a while loop. I think that makes it O(n^2) instead.

Then I found this solution - https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf - on slide 19 - apparantly they are looking for a faster way - but on second step of Step 3, they are looking for all adjacent nodes (inside a while loop), so that makes it O(n^2) too.

So is this case - http://www.geeksforgeeks.org/topological-sorting/

What am I missing here?

Answer 1

has a for each inside a while loop. I think that makes it O(n^2) instead.

If you use an adjacency list representation of your graph, you look at every edge exactly once in the inner loop, so it's O(max {n, m}) = O(n + m).

Of course it is also O(n^2), but that is not a tight upper bound.

they are looking for all adjacent nodes (inside a while loop), so that makes it O(n^2) too.

Again, it's also O(n + m) if you use adjacency lists to represent your graph.