Namaran

Code daily. Without assist.

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 を返します。