# An algorithm for topological sorting based on depth-first search: why do we need two tags?

Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)

function visit(node n)
if n has a permanent mark then return
if n has a temporary mark then stop   (not a DAG)
mark n with a temporary mark
for each node m with an edge from n to m do
visit(m)
remove temporary mark from n
mark n with a permanent mark


I couldn't see the necessity of introducing two tags: permanent and temporary. As far as I can see, the following algorithm would work, using only one tag -- explored.

L ← Empty list that will contain the sorted nodes
while exists nodes without an explored mark do
select an unmarked node n
visit(n)

function visit(node n)
mark n as explored
for each node m with an edge from n to m do
if m is unexplored
visit(m)
if m is explored
stop(not a DAG)

Consider the following graph $$G = (V, E)$$ where $$V = \{1, 2, 3\}, E = \{(1, 3), (2, 3)\}.$$ If your example started at $$1$$, it will add $$3$$ to the list and then it will add $$1$$. In the next step the algorithm will choose $$2$$ as an unvisited vertex, which has an edge to a visited vertex $$3$$. Hence, It will conclude that the graph is not a DAG. However, the graph is a DAG and your algorithm is not always correct.