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 8)

5pub fn grl_3_b(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, (graph, _): @UndirectedGraphScanner::<usize, ()>::new(vs, es));
8    let mut bridge = LowLink::new(&graph).bridge;
9    bridge.sort_unstable();
10    for (u, v) in bridge.into_iter() {
11        pp!(u, v);
12    }
13}

More examples

Hide additional examples

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

5pub fn grl_3_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, (graph, _): @UndirectedGraphScanner::<usize, ()>::new(vs, es));
8    let mut articulation = LowLink::new(&graph).articulation;
9    articulation.sort_unstable();
10    for u in articulation.into_iter() {
11        pp!(u);
12    }
13}

crates/library_checker/src/graph/two_edge_connected_components.rs (line 12)

8pub fn two_edge_connected_components(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, m, edges: [(usize, usize); m]);
11    let graph = UndirectedSparseGraph::from_edges(n, edges);
12    let low_link = LowLink::new(&graph);
13    let mut uf = UnionFind::new(n);
14    for &(mut u, mut v) in &graph.edges {
15        if low_link.ord[u] > low_link.ord[v] {
16            std::mem::swap(&mut u, &mut v);
17        }
18        if low_link.ord[u] >= low_link.low[v] {
19            uf.unite(u, v);
20        }
21    }
22    let groups = uf.all_group_members();
23    pp!(groups.len());
24    for group in groups.into_values() {
25        pp!(group.len(), @it group);
26    }
27}

Source

fn dfs(&mut self, u: usize, parent_eid: 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, !0, &mut 0);
22            }
23        }
24        self_
25    }
26    fn dfs(&mut self, u: usize, parent_eid: 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.neighbors(u) {
33            if a.label == parent_eid {
34                continue;
35            }
36            if self.ord[a.to] == usize::MAX {
37                cnt += 1;
38                self.dfs(a.to, a.label, now_ord);
39                self.low[u] = self.low[u].min(self.low[a.to]);
40                is_articulation |= parent_eid != !0 && self.ord[u] <= self.low[a.to];
41                if self.ord[u] < self.low[a.to] {
42                    self.bridge.push((u.min(a.to), u.max(a.to)));
43                }
44            } else {
45                self.low[u] = self.low[u].min(self.ord[a.to]);
46            }
47        }
48        is_articulation |= parent_eid == !0 && cnt > 1;
49        if is_articulation {
50            self.articulation.push(u);
51        }
52    }