判断图中是否有回路

题目描述：设G＝(V, E)是有向图，请给出算法，判断G中是否有回路，并要求算法的复杂性为O(n+e)，其中n = | V |，e = | E |。（10.0分）

下面是对判断算法的ADL语言描述：

算法Judge_loop(Head , ans )

/遍历图查看是否有回路/

Jl1. [初始化]

    ans=false.

    /计算 count 数组/

    FOR i=1 TO n DO count[i] <- 0;

    FOR i=1 TO n DO

        ( p <- adjacent(Head[i]).

        WHILE p≠^ DO

            (count[VerAdj(p)] <- count[VerAdj(p)] + 1.

            p <- link(p)))

    top <- -1.

    FOR i=1 TO n DO

        IF count[i] =0 THEN

            (count[i] <- top. Top <- i.)

Jl2.[判断是否有回路]

    FOR i=1 TO n DO

        /若循环体尚未被执行n次，栈顶指针已为-1，说明有回路，终止程序/

        IF top=-1 THEN ans=true.

        ELSE

            (j <- top.

            top <- count[top].

            p<-adjacent(Head[i]).

            WHILE p≠^ DO

                (k <- VerAdj(p).

                count[k] <- count[k]-1.

                IF count[k] = 0 THEN

                    (count[k] <- top. Top <- k.)

                p <- link(p))) ▌

​