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

Question

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
    add n to head of L

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)
    add n to head of L

If it's not the case, please tell me where I went wrong within this algorithm.

Answer 1

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.

The reason why we need two kinds of marking is to distinguish cycles from components we already done in previous iterations. Reaching back to an ancestor in the recursion tree means that there is a path going back to a vertex we came from and hence a cycle. Meanwhile an edge to a vertex that is permanently marked (and hence was visited in a previous iteration) can never introduce a cycle, since else we would have reached the current vertex in the same iteration as well.