2022-11-07:给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边。 图用一个大小为 n 下标从 0 开始
节点 一个 2022 开始 11 大小 一条 每个
2023-06-13 09:14:44 时间
2022-11-07:给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边。
图用一个大小为 n 下标从 0 开始的数组 edges 表示,
节点 i 到节点 edgesi 之间有一条有向边。如果节点 i 没有出边,那么 edgesi == -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 {}
执行结果如下:
***
相关文章
- leetcode 1019. 链表中的下一个更大节点 js实现
- Prometheus➕Grafana监控node节点资源情况
- LeetCode 237. 删除链表中的节点
- 给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
- 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙
- 循环双向链表(带头节点)
- 【ES三周年】集群半数以上master节点掉线解决方法
- 【Linux 内核 内存管理】引导内存分配器 bootmem ② ( bootmem_data 结构体源码分析 | bootmem_data 与内存节点 pglist_data 的关联 )
- redis哈希类型_动力节点Java学院整理
- sql server递归子节点、父节点sql查询表结构的实例
- JS removeChild()方法:删除节点
- 一个节点停止Redis集群中的一个节点(redis集群停止)
- 利用Redis缓存节点优化性能(redis缓存节点)
- 如何在 Redis 中高效地删除节点?(redis删除节点)
- 当天蝎多节点服务器遇到OpenStack
- Redis主从节点实现高可用架构,提升数据处理效率(redis主从节点)
- 快速切换Redis节点的实用命令(切换redis节点命令)
- 重启Redis集群节点改变让运行更加稳定(redis集群重启节点)
- 节点Redis集群节点最少需要3个(redis集群最少多少个)
- 使用Redis集群时如何集群节点发现(redis集群怎么发现的)
- 一个Redis集群如何加入一个新的节点(redis集群 加入)
- 增加实现Redis集群的扩容增加一个节点(redis集群一个节点)
- 如何配置Redis多节点集群(redis配置多节点)
- 节点利用Redis智能选择节点(redis选取一个)
- Javascript入门学习第八篇jsdom节点属性说明
- 节点的插入之append()和appendTo()的用法介绍
- Mongodb增加、移除Arbiter节点实例