栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

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

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

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

答案2022-06-03:

拓扑排序。

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

fn main() {
    let sc: Vec = 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 = vec![];
        let mut edges_to: Vec = 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,
    out0: Vec,
    lines: Vec,
    head_edge: Vec,
    queue: Vec,
    mod0: i32,
    n: i32,
}

impl GlobalInfo {
    pub fn new() -> Self {
        let mut in0: Vec = vec![];
        let mut out0: Vec = vec![];
        let mut lines: Vec = vec![];
        let mut head_edge: Vec = vec![];
        let mut queue: Vec = 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, edges_to: &mut Vec, 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代码

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/951166.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号