// Fulkerson reduction: glue chains via matched edges, contract by
// pointer-jumping.

fn parent_pointer_jumping(c: &mut [usize]) {
    let n = c.len();
    let mut changed = true;
    while changed {
        changed = false;
        for i in 0..n {
            let p = c[i];
            if c[p] != p { c[i] = c[p]; changed = true; }
        }
    }
}

fn par_chain_cover_from_matching(match_partner: &[i32]) -> Vec<usize> {
    let n = match_partner.len();
    let mut c: Vec<usize> = (0..n).collect();
    for u in 0..n {
        if match_partner[u] != -1 { c[u] = match_partner[u] as usize; }
    }
    parent_pointer_jumping(&mut c);
    c
}

fn main() {
    let m = [2i32, 4, 0, -1, 1];
    let c = par_chain_cover_from_matching(&m);
    println!("chain id: {:?}", c);
}