深さ優先探索を利用して帰りがけ順を求める

深さ優先探索を利用して帰りがけ順を求めます。

入力

5 4
1 2
1 3
2 4
2 5

実装

function main()
    n, m = parseints()
    global g = [[] for _ ∈ 1:n]

    for _ ∈ 1:m
        a, b = parseints()

        push!(g[a], b)
    end

    global seen = fill(false, n)

    dfs(1)
end

function dfs(vertex)
    seen[vertex] = true

    for next_vertex ∈ g[vertex]
        if seen[next_vertex]
            continue
        end

        dfs(next_vertex)
    end

    @show vertex
end

parseint() = readline() |> x -> parse(Int, x)
parsestring() = readline()
parseints() = readline() |> split |> x -> parse.(Int, x)
parsestrings() = readline() |> split

main()

結果は、次の通りになります。

julia> include("dfs.jl")
5 4
1 2
1 3
2 4
2 5
vertex = 4
vertex = 5
vertex = 2
vertex = 3
vertex = 1
1