competitive/graph/
dulmage_mendelsohn_decomposition.rs

1use super::{BipartiteMatching, DirectedSparseGraph, StronglyConnectedComponent};
2
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}
competitive/graph/dulmage_mendelsohn_decomposition.rs

competitive/graph/
dulmage_mendelsohn_decomposition.rs
