1use std::{collections::VecDeque, mem::swap};
2
3#[derive(Debug, Clone)]
4pub struct BipartiteMatching {
5 left_size: usize,
6 right_size: usize,
7 left_graph: Vec<Vec<usize>>,
8 left_match: Vec<Option<usize>>,
9 right_match: Vec<Option<usize>>,
10 matching_size: usize,
11}
12
13impl BipartiteMatching {
14 pub fn new(left_size: usize, right_size: usize) -> Self {
15 Self {
16 left_size,
17 right_size,
18 left_graph: vec![vec![]; left_size],
19 left_match: vec![None; left_size],
20 right_match: vec![None; right_size],
21 matching_size: 0,
22 }
23 }
24 pub fn add_edge(&mut self, l: usize, r: usize) {
25 assert!(l < self.left_size);
26 assert!(r < self.right_size);
27 self.left_graph[l].push(r);
28 self.matching_size = !0;
29 }
30 pub fn from_edges(left_size: usize, right_size: usize, lr: &[(usize, usize)]) -> Self {
31 let mut deg = vec![0usize; left_size];
32 for &(l, _) in lr {
33 deg[l] += 1;
34 }
35 let mut left_graph: Vec<_> = deg.into_iter().map(Vec::with_capacity).collect();
36 for &(l, r) in lr {
37 assert!(l < left_size);
38 assert!(r < right_size);
39 left_graph[l].push(r);
40 }
41 Self {
42 left_size,
43 right_size,
44 left_graph,
45 left_match: vec![None; left_size],
46 right_match: vec![None; right_size],
47 matching_size: !0,
48 }
49 }
50 pub fn hopcroft_karp(&mut self) {
51 fn bfs(bm: &BipartiteMatching, deq: &mut VecDeque<usize>, level: &mut [usize]) {
52 deq.clear();
53 for (i, r) in bm.left_match.iter().enumerate() {
54 if r.is_none() {
55 deq.push_back(i);
56 level[i] = 0;
57 }
58 }
59 while let Some(l) = deq.pop_front() {
60 for &r in &bm.left_graph[l] {
61 if let Some(nl) = bm.right_match[r] {
62 if level[nl] == !0 {
63 deq.push_back(nl);
64 level[nl] = level[l] + 1;
65 }
66 }
67 }
68 }
69 }
70 fn dfs(
71 bm: &mut BipartiteMatching,
72 l: usize,
73 level: &mut [usize],
74 used: &mut [bool],
75 ) -> bool {
76 used[l] = true;
77 for i in 0..bm.left_graph[l].len() {
78 let r = bm.left_graph[l][i];
79 if let Some(nl) = bm.right_match[r] {
80 if used[nl] || level[l] + 1 != level[nl] || !dfs(bm, nl, level, used) {
81 continue;
82 }
83 }
84 bm.right_match[r] = Some(l);
85 bm.left_match[l] = Some(r);
86 return true;
87 }
88 false
89 }
90 if self.matching_size != !0 {
91 return;
92 }
93 self.matching_size = self.left_match.iter().filter(|r| r.is_some()).count();
94 let mut used = vec![false; self.left_size];
95 let mut level = vec![!0; self.left_size];
96 let mut deq = VecDeque::with_capacity(self.left_size);
97 loop {
98 bfs(self, &mut deq, &mut level);
99 let prev_size = self.matching_size;
100 for l in 0..self.left_size {
101 if self.left_match[l].is_none() {
102 self.matching_size += dfs(self, l, &mut level, &mut used) as usize;
103 }
104 }
105 if self.matching_size == prev_size {
106 break;
107 }
108 for item in level.iter_mut() {
109 *item = !0;
110 }
111 for item in used.iter_mut() {
112 *item = false;
113 }
114 }
115 }
116 pub fn kuhn_multi_start_bfs(&mut self) {
117 if self.matching_size != !0 {
118 return;
119 }
120 self.matching_size = self.left_match.iter().filter(|r| r.is_some()).count();
121 let mut deq = VecDeque::with_capacity(self.left_size);
122 let mut prev = vec![!0usize; self.left_size];
123 let mut root = vec![!0usize; self.left_size];
124 loop {
125 let mut changed = false;
126 for (l, r) in self.left_match.iter().enumerate() {
127 if r.is_none() {
128 root[l] = l;
129 deq.push_back(l);
130 }
131 }
132 while let Some(mut l) = deq.pop_front() {
133 if self.left_match[root[l]].is_some() {
134 continue;
135 }
136 for mut r in self.left_graph[l].iter().cloned() {
137 if let Some(nl) = self.right_match[r] {
138 if prev[nl] == !0 {
139 prev[nl] = l;
140 root[nl] = root[l];
141 deq.push_back(nl);
142 }
143 } else {
144 loop {
145 self.right_match[r] = Some(l);
146 if let Some(nr) = &mut self.left_match[l] {
147 swap(nr, &mut r);
148 l = prev[l];
149 } else {
150 self.left_match[l] = Some(r);
151 break;
152 }
153 }
154 changed = true;
155 self.matching_size += 1;
156 break;
157 }
158 }
159 }
160 if !changed {
161 break;
162 }
163 for item in prev.iter_mut() {
164 *item = !0;
165 }
166 for item in root.iter_mut() {
167 *item = !0;
168 }
169 }
170 }
171 pub fn maximum_matching(&mut self) -> Vec<(usize, usize)> {
172 self.kuhn_multi_start_bfs();
173 self.left_match
174 .iter()
175 .enumerate()
176 .filter_map(|(l, r)| r.map(|r| (l, r)))
177 .collect()
178 }
179 pub fn minimum_edge_cover(&mut self) -> Vec<(usize, usize)> {
180 self.kuhn_multi_start_bfs();
181 let mut res = Vec::with_capacity(self.left_size + self.right_size - self.matching_size);
182 let mut left_used: Vec<_> = self.left_match.iter().map(Option::is_some).collect();
183 let mut right_used: Vec<_> = self.right_match.iter().map(Option::is_some).collect();
184 for (l, lg) in self.left_graph.iter().enumerate() {
185 if let Some(r) = self.left_match[l] {
186 res.push((l, r));
187 }
188 for &r in lg {
189 if !left_used[l] || !right_used[r] {
190 left_used[l] = true;
191 right_used[r] = true;
192 res.push((l, r));
193 }
194 }
195 }
196 res
197 }
198 fn reachable(&mut self) -> (Vec<bool>, Vec<bool>) {
199 #[derive(Clone, Copy)]
200 enum Either {
201 Left(usize),
202 Right(usize),
203 }
204 self.kuhn_multi_start_bfs();
205 let mut left_used = vec![false; self.left_size];
206 let mut right_used = vec![false; self.right_size];
207 let mut deq = VecDeque::new();
208 for (l, r) in self.left_match.iter().enumerate() {
209 if r.is_none() {
210 left_used[l] = true;
211 deq.push_back(Either::Left(l));
212 }
213 }
214 loop {
215 match deq.pop_front() {
216 Some(Either::Left(l)) => {
217 for &r in &self.left_graph[l] {
218 if self.left_match[l] != Some(r) && !right_used[r] {
219 right_used[r] = true;
220 deq.push_back(Either::Right(r));
221 }
222 }
223 }
224 Some(Either::Right(r)) => {
225 if let Some(l) = self.right_match[r] {
226 if !left_used[l] {
227 left_used[l] = true;
228 deq.push_back(Either::Left(l));
229 }
230 }
231 }
232 None => break,
233 }
234 }
235 (left_used, right_used)
236 }
237 pub fn minimum_vertex_cover(&mut self) -> (Vec<usize>, Vec<usize>) {
238 let (left_used, right_used) = self.reachable();
239 (
240 left_used
241 .into_iter()
242 .enumerate()
243 .filter_map(|(l, b)| if !b { Some(l) } else { None })
244 .collect(),
245 right_used
246 .into_iter()
247 .enumerate()
248 .filter_map(|(r, b)| if b { Some(r) } else { None })
249 .collect(),
250 )
251 }
252 pub fn maximum_independent_set(&mut self) -> (Vec<usize>, Vec<usize>) {
253 let (left_used, right_used) = self.reachable();
254 (
255 left_used
256 .into_iter()
257 .enumerate()
258 .filter_map(|(l, b)| if b { Some(l) } else { None })
259 .collect(),
260 right_used
261 .into_iter()
262 .enumerate()
263 .filter_map(|(r, b)| if !b { Some(r) } else { None })
264 .collect(),
265 )
266 }
267}
268
269#[cfg(test)]
270mod tests {
271 use super::*;
272 use crate::{chmax, chmin, data_structure::UnionFind, rand, tools::Xorshift};
273
274 fn gen_graph(n: usize, m: usize) -> Vec<(usize, usize)> {
275 let mut rng = Xorshift::default();
276 let mut uf = UnionFind::new(n + m);
277 let mut lr = vec![];
278 while uf.size(0) < n + m {
279 rand!(rng, l: 0..n, r: 0..m);
280 uf.unite(l, r + n);
281 lr.push((l, r));
282 }
283 lr.sort_unstable();
284 lr.dedup();
285 lr
286 }
287
288 const Q: usize = 100;
289 const N: usize = 8;
290 const M: usize = 8;
291
292 #[test]
293 fn test_minimum_edge_cover() {
294 let mut rng = Xorshift::default();
295 for _ in 0..Q {
296 rand!(rng, n: 4..=N, m: 4..=M);
297 let lr = gen_graph(n, m);
298 let mut dp = vec![vec![!0usize; 1 << m]; 1 << n];
299 dp[0][0] = 0;
300 for bitl in 0usize..1 << n {
301 for bitr in 0usize..1 << m {
302 if dp[bitl][bitr] == !0 {
303 continue;
304 }
305 for &(l, r) in &lr {
306 chmin!(dp[bitl | (1 << l)][bitr | (1 << r)], dp[bitl][bitr] + 1);
307 }
308 }
309 }
310 let cover = BipartiteMatching::from_edges(n, m, &lr).minimum_edge_cover();
311 assert_eq!(*dp.last().unwrap().last().unwrap(), cover.len());
312 let mut left_used = vec![false; n];
313 let mut right_used = vec![false; m];
314 for (l, r) in cover {
315 left_used[l] = true;
316 right_used[r] = true;
317 }
318 assert!(left_used.iter().all(|&b| b));
319 assert!(right_used.iter().all(|&b| b));
320 }
321 }
322
323 #[test]
324 fn test_minimum_vertex_cover() {
325 let mut rng = Xorshift::default();
326 for _ in 0..Q {
327 rand!(rng, n: 4..=N, m: 4..=M);
328 let lr = gen_graph(n, m);
329 let mut ans = !0usize;
330 for bitl in 0usize..1 << n {
331 for bitr in 0usize..1 << m {
332 if lr
333 .iter()
334 .all(|&(l, r)| bitl & (1 << l) != 0 || bitr & (1 << r) != 0)
335 {
336 chmin!(ans, (bitl.count_ones() + bitr.count_ones()) as usize);
337 }
338 }
339 }
340 let set = BipartiteMatching::from_edges(n, m, &lr).minimum_vertex_cover();
341 assert_eq!(ans, set.0.len() + set.1.len());
342 for (l, r) in lr {
343 assert!(set.0.contains(&l) || set.1.contains(&r));
344 }
345 }
346 }
347
348 #[test]
349 fn test_maximum_independent_set() {
350 let mut rng = Xorshift::default();
351 for _ in 0..Q {
352 rand!(rng, n: 4..=N, m: 4..=M);
353 let lr = gen_graph(n, m);
354 let mut ans = 0usize;
355 for bitl in 0usize..1 << n {
356 for bitr in 0usize..1 << m {
357 if lr
358 .iter()
359 .all(|&(l, r)| bitl & (1 << l) == 0 || bitr & (1 << r) == 0)
360 {
361 chmax!(ans, (bitl.count_ones() + bitr.count_ones()) as usize);
362 }
363 }
364 }
365 let set = BipartiteMatching::from_edges(n, m, &lr).maximum_independent_set();
366 assert_eq!(ans, set.0.len() + set.1.len());
367 for (l, r) in lr {
368 assert!(!set.0.contains(&l) || !set.1.contains(&r));
369 }
370 }
371 }
372}