Struct LowLink

Source

pub struct LowLink<'a> {
    graph: &'a UndirectedSparseGraph,
    pub low: Vec<usize>,
    pub ord: Vec<usize>,
    pub articulation: Vec<usize>,
    pub bridge: Vec<(usize, usize)>,
}

Fields§

§graph: &'a UndirectedSparseGraph§low: Vec<usize>§ord: Vec<usize>§articulation: Vec<usize>§bridge: Vec<(usize, usize)>

Implementations§

Source §

impl<'a> LowLink<'a>

Source

pub fn new(graph: &'a UndirectedSparseGraph) -> Self

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_3_b.rs (line 10)

6pub fn grl_3_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, (graph, _): @UndirectedGraphScanner::<usize, ()>::new(vs, es));
10    let mut bridge = LowLink::new(&graph).bridge;
11    bridge.sort_unstable();
12    for (u, v) in bridge.into_iter() {
13        writeln!(writer, "{} {}", u, v).ok();
14    }
15}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_3_a.rs (line 10)

6pub fn grl_3_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, (graph, _): @UndirectedGraphScanner::<usize, ()>::new(vs, es));
10    let mut articulation = LowLink::new(&graph).articulation;
11    articulation.sort_unstable();
12    for u in articulation.into_iter() {
13        writeln!(writer, "{}", u).ok();
14    }
15}

Source

fn dfs(&mut self, u: usize, p: usize, now_ord: &mut usize)

Examples found in repository ?

crates/competitive/src/graph/low_link.rs (line 21)

11    pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
12        let mut self_ = Self {
13            graph,
14            low: vec![0; graph.vertices_size()],
15            ord: vec![usize::MAX; graph.vertices_size()],
16            articulation: vec![],
17            bridge: vec![],
18        };
19        for u in graph.vertices() {
20            if self_.ord[u] == usize::MAX {
21                self_.dfs(u, graph.vertices_size(), &mut 0);
22            }
23        }
24        self_
25    }
26    fn dfs(&mut self, u: usize, p: usize, now_ord: &mut usize) {
27        self.low[u] = *now_ord;
28        self.ord[u] = *now_ord;
29        *now_ord += 1;
30        let mut is_articulation = false;
31        let mut cnt = 0;
32        for a in self.graph.adjacencies(u) {
33            if self.ord[a.to] == usize::MAX {
34                cnt += 1;
35                self.dfs(a.to, u, now_ord);
36                self.low[u] = self.low[u].min(self.low[a.to]);
37                is_articulation |= p < self.graph.vertices_size() && self.ord[u] <= self.low[a.to];
38                if self.ord[u] < self.low[a.to] {
39                    self.bridge.push((u.min(a.to), u.max(a.to)));
40                }
41            } else if a.to != p {
42                self.low[u] = self.low[u].min(self.ord[a.to]);
43            }
44        }
45        is_articulation |= p == self.graph.vertices_size() && cnt > 1;
46        if is_articulation {
47            self.articulation.push(u);
48        }
49    }