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

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

``````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 {}
``````

(=￣ω￣=)··· 暂无内容！

172

10

16

5