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代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_3_week/Code01_LongestCycleInGraph1.java)
