Muszę opracować algorytm O (| V | + | E |) powiązany z sortowaniem topologicznym, który w ukierunkowanym wykresie acyklicznym (DAG) określa liczbę ścieżek od każdego wierzchołka wykresu do t (t jest węzłem z out-stopień 0). Opracowałem modyfikację DFS w następujący sposób:

DFS(G,t):
    for each vertex u ∈ V do
        color(u) = WHITE
        paths_to_t(u) = 0
    for each vertex u ∈ V do
        if color(u) == WHITE then
            DFS-Visit(u,t)

DFS-Visit(u,t):
    color(u) = GREY
    for each v ∈ neighbors(u) do
        if v == t then
            paths_to_t(u) = paths_to_t(u) + 1
        else then
            if color(v) == WHITE then
                DFS-Visit(v)
            paths_to_t(u) = paths_to_t(u) + paths_to_t(v)
    color(u) = BLACK

Ale nie jestem pewien, czy ten algorytm jest powiązany z sortowaniem topologicznym lub czy powinienem zrestrukturyzować moją pracę z innym punktem widzenia.