incounter variables can be done with simple traversal of the graphwhich takes ( mtime we use the decorator pattern to associate counter attributes with the vertices say that vertex is visited by the topological sorting algorithm when is removed from the stack vertex can be visited only when incounter ( which implies that all its predecessors (vertices with outgoing edges into uwere previously visited as consequenceany vertex that is on directed cycle will never be visitedand any other vertex will be visited exactly once the algorithm traverses all the outgoing edges of each visited vertex onceso its running time is proportional to the number of outgoing edges of the visited vertices thereforethe algorithm runs in ( mtime regarding the space usageobserve that the stack and the incounter variables attached to the vertices use (nspace as side effectthe topological sorting algorithm of code fragment also tests whether the input digraph is acyclic indeedif the algorithm terminates without ordering all the verticesthen the subgraph of the vertices that have not been ordered must contain directed cycle figure example of run of algorithm topologicalsort (code fragment )(ainitial configuration( -iafter each while-loop iteration the vertex labels show the vertex number and the current incounter value the edges traversed are shown with dashed blue arrows thick lines denote the vertex and edges examined in the current iteration