haar_lib/graph/cycle/
directed_shortest.rs

1//! 有向グラフで単一始点の最短サイクルを求める。
2//! # Problems
3//! - [ABC 142 F - Pure](https://atcoder.jp/contests/abc142/tasks/abc142_f)
4//! - <https://atcoder.jp/contests/abc376/tasks/abc376_d>
5
6use crate::graph::{bfs::*, *};
7
8/// 有向グラフで単一始点の最短サイクルを求める。
9///
10/// **Time complexity** $O(V + E)$
11pub fn directed_shortest_cycle<E: EdgeTrait>(
12    g: &Graph<Directed, E>,
13    src: usize,
14) -> Option<Vec<&E>> {
15    let res = bfs(g, Some(src));
16    let p = res
17        .iter()
18        .flatten()
19        .flat_map(|(d, e)| {
20            e.map(|e| {
21                g.nodes[e.to()]
22                    .edges
23                    .iter()
24                    .find(|e| e.to() == src)
25                    .map(|e_src| (d, e, e_src))
26            })
27            .flatten()
28        })
29        .min_by_key(|(d, _, _)| *d);
30
31    p.map(|(_, e, e_src)| {
32        let mut ret = vec![];
33        let mut cur = e.to();
34
35        ret.push(e_src);
36
37        while cur != src {
38            let e = res[cur].unwrap().1.unwrap();
39            ret.push(e);
40            cur = e.from();
41        }
42
43        ret.reverse();
44        ret
45    })
46}