2022-06-03：a -＞ b，代表a在食物链中被b捕食，给定一个有向无环图，返回这个图中从最初级动物到最顶级捕食者的食物链有几条。

原创

福大大架构师每日一题

发布于 2022-06-03 21:25:56

2160

发布于 2022-06-03 21:25:56

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-06-03：a -> b，代表a在食物链中被b捕食，

给定一个有向无环图，返回这个图中从最初级动物到最顶级捕食者的食物链有几条。

来自理想汽车。

答案2022-06-03：

拓扑排序。

代码用rust编写。代码如下：

fn main() {
    let sc: Vec<i32> = vec![5, 7, 1, 2, 1, 3, 2, 3, 3, 5, 2, 5, 4, 5, 3, 4];
    let mut ii: i32 = 0;
    while ii < sc.len() as i32 {
        let mut info = GlobalInfo::new();
        info.n = sc[ii as usize];
        ii += 1;
        let m: i32 = sc[ii as usize];
        ii += 1;
        let mut pre_edge: Vec<i32> = vec![];
        let mut edges_to: Vec<i32> = vec![];
        for _ in 0..m + 1 {
            pre_edge.push(0);
            edges_to.push(0);
        }
        for i in 1..=m {
            let from = sc[ii as usize];
            ii += 1;
            let to = sc[ii as usize];
            ii += 1;
            edges_to[i as usize] = to;
            pre_edge[i as usize] = info.head_edge[from as usize];
            info.head_edge[from as usize] = i;
            info.out0[from as usize] = true;
            info.in0[to as usize] += 1;
        }
        let ans = how_many_ways(&mut pre_edge, &mut edges_to, &mut info);
        println!("ans = {}", ans);
    }
}

pub struct GlobalInfo {
    in0: Vec<i32>,
    out0: Vec<bool>,
    lines: Vec<i32>,
    head_edge: Vec<i32>,
    queue: Vec<i32>,
    mod0: i32,
    n: i32,
}

impl GlobalInfo {
    pub fn new() -> Self {
        let mut in0: Vec<i32> = vec![];
        let mut out0: Vec<bool> = vec![];
        let mut lines: Vec<i32> = vec![];
        let mut head_edge: Vec<i32> = vec![];
        let mut queue: Vec<i32> = vec![];
        let mod0: i32 = 80112002;
        let n: i32 = 0;
        for _i in 0..5001 {
            in0.push(0);
            out0.push(false);
            lines.push(0);
            head_edge.push(0);
            queue.push(0);
        }
        Self {
            in0,
            out0,
            lines,
            head_edge,
            queue,
            mod0,
            n,
        }
    }
}

fn how_many_ways(pre_edge: &mut Vec<i32>, edges_to: &mut Vec<i32>, info: &mut GlobalInfo) -> i32 {
    let mut ql = 0;
    let mut qr = 0;
    for i in 1..info.n {
        if info.in0[i as usize] == 0 {
            info.queue[qr as usize] = i;
            qr += 1;
            info.lines[i as usize] = 1;
        }
    }
    while ql < qr {
        let cur = info.queue[ql];
        ql += 1;
        let mut edge = info.head_edge[cur as usize];
        while edge != 0 {
            let next = edges_to[edge as usize];
            info.lines[next as usize] =
                (info.lines[next as usize] + info.lines[cur as usize]) % info.mod0;
            info.in0[next as usize] -= 1;
            if info.in0[next as usize] == 0 {
                info.queue[qr] = next;
                qr += 1;
            }
            edge = pre_edge[edge as usize];
        }
    }
    let mut ans = 0;
    for i in 1..=info.n {
        if !info.out0[i as usize] {
            ans = (ans + info.lines[i as usize]) % info.mod0;
        }
    }
    return ans;
}

执行结果如下：