Struct StronglyConnectedComponent

Source

pub struct StronglyConnectedComponent<'a> { /* private fields */ }

Implementations§

Source §

impl<'a> StronglyConnectedComponent<'a>

Source

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

Examples found in repository ?

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

6pub fn grl_3_c(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, _): @DirectedGraphScanner::<usize, ()>::new(vs, es));
10    let scc = StronglyConnectedComponent::new(&graph);
11    scan!(scanner, q);
12    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
13        writeln!(writer, "{}", (scc[u] == scc[v]) as u32).ok();
14    }
15}

More examples

Hide additional examples

crates/competitive/src/graph/two_satisfiability.rs (line 35)

33    pub fn two_satisfiability(self) -> Option<Vec<bool>> {
34        let graph = DirectedSparseGraph::from_edges(self.vsize * 2, self.edges);
35        let scc = StronglyConnectedComponent::new(&graph);
36        let mut res = vec![false; self.vsize];
37        for i in 0..self.vsize {
38            if scc[i * 2] == scc[i * 2 + 1] {
39                return None;
40            }
41            res[i] = scc[i * 2] > scc[i * 2 + 1];
42        }
43        Some(res)
44    }

crates/library_checker/src/graph/scc.rs (line 11)

6pub fn scc(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, edges: [(usize, usize); es]);
10    let graph = DirectedSparseGraph::from_edges(vs, edges);
11    let scc = StronglyConnectedComponent::new(&graph);
12    let comp = scc.components();
13    writeln!(writer, "{}", comp.len()).ok();
14    for vs in comp.into_iter() {
15        iter_print!(writer, vs.len(), @it vs);
16    }
17}

crates/competitive/src/graph/dulmage_mendelsohn_decomposition.rs (line 19)

3pub fn dulmage_mendelsohn_decomposition(
4    l: usize,
5    r: usize,
6    edges: &[(usize, usize)],
7) -> Vec<(Vec<usize>, Vec<usize>)> {
8    let mut matching = vec![!0usize; l + r];
9    let mut medges: Vec<_> = edges.iter().map(|&(u, v)| (u, v + l)).collect();
10    for (u, v) in BipartiteMatching::from_edges(l, r, edges).maximum_matching() {
11        medges.push((v + l, u));
12        matching[u] = v + l;
13        matching[v + l] = u;
14    }
15    let rmedges = medges.iter().map(|&(u, v)| (v, u)).collect();
16
17    let g = DirectedSparseGraph::from_edges(l + r, medges);
18    let rg = DirectedSparseGraph::from_edges(l + r, rmedges);
19    let scc = StronglyConnectedComponent::new(&g);
20    let csize = scc.size();
21
22    let mut cmap = vec![!0usize - 1; csize];
23    let mut visited = vec![false; l + r];
24    let mut stack = vec![];
25    for u in 0..l {
26        if matching[u] == !0 && !visited[u] {
27            visited[u] = true;
28            stack.push(u);
29            while let Some(u) = stack.pop() {
30                cmap[scc[u]] = !0;
31                for a in g.adjacencies(u) {
32                    if !visited[a.to] {
33                        visited[a.to] = true;
34                        stack.push(a.to);
35                    }
36                }
37            }
38        }
39    }
40    for u in l..l + r {
41        if matching[u] == !0 && !visited[u] {
42            visited[u] = true;
43            stack.push(u);
44            while let Some(u) = stack.pop() {
45                cmap[scc[u]] = 0;
46                for a in rg.adjacencies(u) {
47                    if !visited[a.to] {
48                        visited[a.to] = true;
49                        stack.push(a.to);
50                    }
51                }
52            }
53        }
54    }
55
56    let mut nset = 1usize;
57    for v in &mut cmap {
58        if *v == !0 - 1 {
59            *v = nset;
60            nset += 1;
61        }
62    }
63    for v in &mut cmap {
64        if *v == !0 {
65            *v = nset;
66        }
67    }
68    nset += 1;
69
70    let mut groups = vec![(vec![], vec![]); nset];
71    for u in 0..l {
72        if matching[u] != !0 {
73            let c = cmap[scc[u]];
74            groups[c].0.push(u);
75            groups[c].1.push(matching[u] - l);
76        }
77    }
78    for u in 0..l {
79        if matching[u] == !0 {
80            let c = cmap[scc[u]];
81            groups[c].0.push(u);
82        }
83    }
84    for u in 0..r {
85        if matching[u + l] == !0 {
86            let c = cmap[scc[u + l]];
87            groups[c].1.push(u);
88        }
89    }
90    groups
91}

Source §

impl StronglyConnectedComponent<'_>

Source

pub fn gen_cgraph(&self) -> DirectedSparseGraph

Source

pub fn components(&self) -> Vec<Vec<usize>>

Examples found in repository ?

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

6pub fn scc(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, edges: [(usize, usize); es]);
10    let graph = DirectedSparseGraph::from_edges(vs, edges);
11    let scc = StronglyConnectedComponent::new(&graph);
12    let comp = scc.components();
13    writeln!(writer, "{}", comp.len()).ok();
14    for vs in comp.into_iter() {
15        iter_print!(writer, vs.len(), @it vs);
16    }
17}

Source

pub fn has_loop(&self) -> bool

Source

pub fn size(&self) -> usize

Examples found in repository ?

crates/competitive/src/graph/strongly_connected_component.rs (line 79)

65    pub fn gen_cgraph(&self) -> DirectedSparseGraph {
66        let mut used = std::collections::HashSet::new();
67        let mut edges = vec![];
68        for u in self.graph.vertices() {
69            for a in self.graph.adjacencies(u) {
70                if self.comp[u] != self.comp[a.to] {
71                    let (x, y) = (self.comp[u], self.comp[a.to]);
72                    if !used.contains(&(x, y)) {
73                        used.insert((x, y));
74                        edges.push((x, y));
75                    }
76                }
77            }
78        }
79        DirectedSparseGraph::from_edges(self.size(), edges)
80    }
81    pub fn components(&self) -> Vec<Vec<usize>> {
82        let mut counts = vec![0; self.size()];
83        for &x in self.comp.iter() {
84            counts[x] += 1;
85        }
86        let mut groups = vec![vec![]; self.size()];
87        for (g, c) in groups.iter_mut().zip(counts.into_iter()) {
88            g.reserve(c);
89        }
90        for u in self.graph.vertices() {
91            groups[self[u]].push(u);
92        }
93        groups
94    }

More examples

Hide additional examples

crates/competitive/src/graph/dulmage_mendelsohn_decomposition.rs (line 20)

3pub fn dulmage_mendelsohn_decomposition(
4    l: usize,
5    r: usize,
6    edges: &[(usize, usize)],
7) -> Vec<(Vec<usize>, Vec<usize>)> {
8    let mut matching = vec![!0usize; l + r];
9    let mut medges: Vec<_> = edges.iter().map(|&(u, v)| (u, v + l)).collect();
10    for (u, v) in BipartiteMatching::from_edges(l, r, edges).maximum_matching() {
11        medges.push((v + l, u));
12        matching[u] = v + l;
13        matching[v + l] = u;
14    }
15    let rmedges = medges.iter().map(|&(u, v)| (v, u)).collect();
16
17    let g = DirectedSparseGraph::from_edges(l + r, medges);
18    let rg = DirectedSparseGraph::from_edges(l + r, rmedges);
19    let scc = StronglyConnectedComponent::new(&g);
20    let csize = scc.size();
21
22    let mut cmap = vec![!0usize - 1; csize];
23    let mut visited = vec![false; l + r];
24    let mut stack = vec![];
25    for u in 0..l {
26        if matching[u] == !0 && !visited[u] {
27            visited[u] = true;
28            stack.push(u);
29            while let Some(u) = stack.pop() {
30                cmap[scc[u]] = !0;
31                for a in g.adjacencies(u) {
32                    if !visited[a.to] {
33                        visited[a.to] = true;
34                        stack.push(a.to);
35                    }
36                }
37            }
38        }
39    }
40    for u in l..l + r {
41        if matching[u] == !0 && !visited[u] {
42            visited[u] = true;
43            stack.push(u);
44            while let Some(u) = stack.pop() {
45                cmap[scc[u]] = 0;
46                for a in rg.adjacencies(u) {
47                    if !visited[a.to] {
48                        visited[a.to] = true;
49                        stack.push(a.to);
50                    }
51                }
52            }
53        }
54    }
55
56    let mut nset = 1usize;
57    for v in &mut cmap {
58        if *v == !0 - 1 {
59            *v = nset;
60            nset += 1;
61        }
62    }
63    for v in &mut cmap {
64        if *v == !0 {
65            *v = nset;
66        }
67    }
68    nset += 1;
69
70    let mut groups = vec![(vec![], vec![]); nset];
71    for u in 0..l {
72        if matching[u] != !0 {
73            let c = cmap[scc[u]];
74            groups[c].0.push(u);
75            groups[c].1.push(matching[u] - l);
76        }
77    }
78    for u in 0..l {
79        if matching[u] == !0 {
80            let c = cmap[scc[u]];
81            groups[c].0.push(u);
82        }
83    }
84    for u in 0..r {
85        if matching[u + l] == !0 {
86            let c = cmap[scc[u + l]];
87            groups[c].1.push(u);
88        }
89    }
90    groups
91}