Namaran

Code daily. Without assist.

2026-10-30

valid_order.rs

fn is_valid_order(order: &[usize], deps: &[(usize, usize)]) -> bool {
}

order は作業 0 から order.len() - 1 までを1回ずつ並べた順番で、deps の組 (a, b) は「作業 a は作業 b より前にする」という条件です。order がすべての条件を守っていれば true、1つでも破っていれば false を返す is_valid_order を書いてください。deps が空なら true です。

入力例 1

is_valid_order(&[2, 0, 1], &[(0, 1), (2, 1)])

出力例 1

true

入力例 2

is_valid_order(&[1, 0, 2], &[(0, 1)])

出力例 2

false

入力例 3

is_valid_order(&[0, 1], &[])

出力例 3

true
Reference
fn is_valid_order(order: &[usize], deps: &[(usize, usize)]) -> bool {
    let mut pos = vec![0; order.len()];
    for (i, &task) in order.iter().enumerate() {
        pos[task] = i;
    }
    deps.iter().all(|&(before, after)| pos[before] < pos[after])
}

条件 (a, b) を確かめるには、a と b が order の何番目にあるかを知る必要があります。そのたびに order を探すと、条件1つごとに並び全体をなめることになるので、先に pos[task] に作業 task の位置を書いた表を作ります。order は各作業を1回ずつ含むので、表の要素はちょうど1回ずつ埋まります。

表ができれば、条件ごとの確認は pos[before] < pos[after] の比較1回で済みます。all は1つでも false が出た時点で止まり、deps が空なら一度も比べずに true を返すので、空の場合を別に書く必要はありません。

掲載したのは参考実装で、唯一の正解ではありません。order.iter().position で毎回位置を探す書き方でも結果は同じで、作業の数が少なければそれで十分です。