2022-11-07：给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点

2022-11-07：给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。
图用一个大小为 n 下标从 0 开始的数组 edges 表示，
节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。
请你返回图中的 最长 环，如果没有任何环，请返回 -1 。
输入：edges = [3,3,4,2,3]。
输出：3。

答案2022-11-07：

一个环指的是起点和终点是 同一个 节点的路径。
用强联通分量。

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

use std::iter::repeat;
impl Solution {
    pub fn longest_cycle(edges: Vec<i32>) -> i32 {
        let n = edges.len() as i32;
        let mut graph: Vec<Vec<i32>> = repeat(vec![]).take(n as usize).collect();
        for i in 0..n {
            if edges[i as usize] != -1 {
                graph[i as usize].push(edges[i as usize]);
            }
        }
        let mut connected_components = StronglyConnectedComponents::new(graph);
        let m = connected_components.get_sccn() + 1;
        let mut cnt: Vec<i32> = repeat(0).take(m as usize).collect();
        let scc = connected_components.get_scc();
        for i in 0..n {
            cnt[scc[i as usize] as usize] += 1;
        }
        let mut ans = -1;
        for count in cnt.iter() {
            ans = get_max(ans, if *count > 1 { *count } else { -1 });
        }
        return ans;
    }
}

struct StronglyConnectedComponents {
    nexts: Vec<Vec<i32>>,
    n: i32,
    stack_size: i32,
    cnt: i32,
    sccn: i32,
    stack: Vec<i32>,
    dfn: Vec<i32>,
    low: Vec<i32>,
    scc: Vec<i32>,
}
impl StronglyConnectedComponents {
    pub fn new(edges: Vec<Vec<i32>>) -> Self {
        let mut ans: StronglyConnectedComponents = StronglyConnectedComponents {
            nexts: edges,
            n: 0,
            stack_size: 0,
            cnt: 0,
            sccn: 0,
            stack: vec![],
            dfn: vec![],
            low: vec![],
            scc: vec![],
        };
        ans.init();
        ans.scc();
        return ans;
    }

    fn init(&mut self) {
        self.n = self.nexts.len() as i32;
        self.stack_size = 0;
        self.cnt = 0;
        self.sccn = 0;
        self.stack = repeat(0).take(self.n as usize).collect();
        self.dfn = repeat(0).take(self.n as usize).collect();
        self.low = repeat(0).take(self.n as usize).collect();
        self.scc = repeat(0).take(self.n as usize).collect();
    }

    fn scc(&mut self) {
        for i in 0..self.n {
            if self.dfn[i as usize] == 0 {
                self.tarjan(i);
            }
        }
    }

    fn tarjan(&mut self, p: i32) {
        self.cnt += 1;
        self.dfn[p as usize] = self.cnt;
        self.low[p as usize] = self.dfn[p as usize];
        self.stack[self.stack_size as usize] = p;
        self.stack_size += 1;
        for q in self.nexts[p as usize].clone().iter() {
            if self.dfn[*q as usize] == 0 {
                self.tarjan(*q);
            }
            if self.scc[*q as usize] == 0 {
                self.low[p as usize] = get_min(self.low[p as usize], self.low[*q as usize]);
            }
        }
        if self.low[p as usize] == self.dfn[p as usize] {
            self.sccn += 1;
            let mut top = 0;

            self.stack_size -= 1;
            top = self.stack[self.stack_size as usize];
            self.scc[top as usize] = self.sccn;
            while top != p {
                self.stack_size -= 1;
                top = self.stack[self.stack_size as usize];
                self.scc[top as usize] = self.sccn;
            }
        }
    }

    fn get_scc(&mut self) -> &Vec<i32> {
        return &self.scc;
    }

    fn get_sccn(&mut self) -> i32 {
        return self.sccn;
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn main() {
    let edges = vec![3, 3, 4, 2, 3];
    let ans = Solution::longest_cycle(edges);
    println!("ans = {}", ans);
    let edges = vec![2, -1, 3, 1];
    let ans = Solution::longest_cycle(edges);
    println!("ans = {}", ans);
}

struct Solution {}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接