algorithm - Time complexity of finding whether graph has a unique topological order -

i have algorithm finding whether directed graph has unique topological order

1. initialise list l
2. find vertex v sink in graph (sink = vertex not going ordered edges)
3. from graph remove edges going v , vertex v
4. add v l
5. if there vertices left in graph go step number 2

at end have topological order of vertices in l. if can choose more 1 vertex in step number 2 topological order not unique. if got stuck in of steps before graph empty means graph has no topological order @ all.

i assumed time complexity of algorithm o(n), n number of vertices in graph apparently not right.

let m number of edges, , n number of vertices. naive implementation of algorithm o(nm). if implement step 2 iterating on set of edges o(m) iteration within loop executed n times.

however, can in time complexity o(n+m) follows. assume vertex stored integer , edge stored pair of integers tail , head.

step a

in addition l, initialise following

(a) array a 1 slot each vertex. array should store each vertex i list of vertices pointing towards i.

(b) stack s of vertices sinks (so can removed).

(c) array b, again 1 slot each vertex. array should store each vertex i number of edges point away i. when number drops zero, corresponding vertex must sink can added s.

step b

start iterating on set of edges. each edge e: -> j increment b[i] 1 , add e list a[j]. iteration o(m).

step c

iterate on array b , if b[i] == 0, add i stack s. o(m).

step d

step d while loop

while (s not empty) {  

remove first sink i s , add l. because have list a[i] know edges point i. each 1 of these edges e: j-> i remove edge subtracting 1 b[j]. if value of b[j] has dropped zero, add j s

}. 

at end of step d sinks have been removed. step d o(n+m) because each vertex removed @ once, , each edge read @ once.