Struct StronglyConnectedComponent

Source

pub struct StronglyConnectedComponent<'a> {
    graph: &'a DirectedSparseGraph,
    csize: usize,
    comp: Vec<usize>,
}

Fields§

§graph: &'a DirectedSparseGraph§csize: usize§comp: Vec<usize>

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

5pub fn grl_3_c(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, (graph, _): @DirectedGraphScanner::<usize, ()>::new(vs, es));
8    let scc = StronglyConnectedComponent::new(&graph);
9    sc!(q);
10    for (u, v) in sv!([(usize, usize); iter q]) {
11        pp!((scc[u] == scc[v]) as u32);
12    }
13}

More examples

Hide additional examples

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

5pub fn scc(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, edges: [(usize, usize); es]);
8    let graph = DirectedSparseGraph::from_edges(vs, edges);
9    let scc = StronglyConnectedComponent::new(&graph);
10    let comp = scc.components();
11    pp!(comp.len());
12    for vs in comp.into_iter() {
13        pp!(vs.len(), @it vs);
14    }
15}

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/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.neighbors(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.neighbors(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 10)

5pub fn scc(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, edges: [(usize, usize); es]);
8    let graph = DirectedSparseGraph::from_edges(vs, edges);
9    let scc = StronglyConnectedComponent::new(&graph);
10    let comp = scc.components();
11    pp!(comp.len());
12    for vs in comp.into_iter() {
13        pp!(vs.len(), @it vs);
14    }
15}

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

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

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.neighbors(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.neighbors(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}