2026-10-30
build_order.rs
fn visit(task: usize, deps: &[Vec<usize>], done: &mut Vec<bool>, order: &mut Vec<usize>) {
if done[task] {
return;
}
done[task] = true;
for &d in &deps[task] {
visit(d, deps, done, order);
}
order.push(task);
}
fn main() {
let deps = vec![vec![2, 1], vec![3], vec![3], vec![]];
let mut done = vec![false; 4];
let mut order = Vec::new();
visit(0, &deps, &mut done, &mut order);
println!("{order:?}");
}
これは何を出力するでしょうか?
Answer
[3, 2, 1, 0] です。
deps[t] は作業 t の前に済ませる作業の一覧で、visit はその作業をすべてたどり終えてから、最後に order.push(task) で自分を並べます。done は、たどり始めた作業を二度たどらないための印です。
visit(0) は deps[0] の先頭の2から進みます。visit(2) は3をたどり、3には前提が無いので最初に3が並び、戻って2が並びます。続く visit(1) の前提3はもう done なのですぐに戻り、1が並びます。0の前提をすべてたどり終えたところで、最後に0が並びます。
どの作業も、前提をすべて並べ終えた後でしか push されないので、出来上がった並びでは前提の作業がいつも先にあり、この順に作業すれば依存関係を守れます。