💨
深さ優先探索を利用して帰りがけ順を求める
深さ優先探索を利用して帰りがけ順を求めます。
入力
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
Discussion