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

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;

}

执行结果如下：

左神java代码

2022-06-03：a -＞ b，代表a在食物链中被b捕食， 给定一个有向无环图，返回这个图中从最初级动物到最顶级捕食者的食物链有几条。 来自理想汽车。的相关教程结束。