2026-10-30
topo.rs
fn topo(next: &[Vec<usize>]) -> Option<Vec<usize>> {
let mut indeg = vec![0; next.len()];
next.iter().flatten().for_each(|&b| indeg[b] += 1);
let mut ready: Vec<usize> = (0..next.len()).filter(|&v| indeg[v] == 0).collect();
let mut order = Vec::new();
while let Some(v) = ready.pop() {
order.push(v);
for &b in &next[v] {
indeg[b] -= 1;
if indeg[b] == 0 {
ready.push(b);
}
}
}
Some(order)
}
fn main() {
println!("{:?}", topo(&[vec![1], vec![2], vec![3], vec![1]]));
}
topo は、next[v] を「作業 v の後にする作業」の一覧として、すべての作業を依存関係を守る順に並べ、そのような並びが無いときは None を返すつもりの関数です。main の依存関係は 1→2→3→1 と輪になっているので、本来は None と出力されるはずが、いまは Some([0]) と出力されます。
Answer
Wrong
Some(order)
indeg[v] は、作業 v より前にする作業のうち、まだ並べていないものの数です。0になった作業から並べ、並べた作業の後にある作業の indeg を1つずつ減らします。main の入力では1、2、3がそれぞれ輪の中の1つ前の作業を待っていて、0を並べて1の indeg が1つ減っても、3から来る分が残ります。輪の中の作業はどれも0にならないまま ready が空になり、並びは [0] で止まります。Some(order) はそれを確かめずに返すので、作業が3つ落ちた並びが成功として返ります。
Right
(order.len() == next.len()).then_some(order)
輪が無ければ、どの作業もいつかは indeg が0になって並ぶので、order の長さは作業の数と同じになります。長さが足りないのは輪がある場合だけなので、長さが等しいときだけ Some を返し、そうでなければ None を返します。