competitive/graph/
general_matching.rs1use std::collections::VecDeque;
2
3#[derive(Debug, Clone)]
4pub struct GeneralMatching {
5 size: usize,
6 graph: Vec<Vec<usize>>,
7 mate: Vec<usize>,
8 matching_size: usize,
9}
10
11impl GeneralMatching {
12 pub fn new(size: usize) -> Self {
13 Self {
14 size,
15 graph: vec![vec![]; size],
16 mate: vec![!0; size],
17 matching_size: 0,
18 }
19 }
20 pub fn add_edge(&mut self, u: usize, v: usize) {
21 assert!(u < self.size);
22 assert!(v < self.size);
23 if u == v {
24 return;
25 }
26 self.graph[u].push(v);
27 self.graph[v].push(u);
28 self.matching_size = !0;
29 }
30 pub fn from_edges(size: usize, edges: &[(usize, usize)]) -> Self {
31 let mut this = Self::new(size);
32 for &(u, v) in edges {
33 this.add_edge(u, v);
34 }
35 this
36 }
37 pub fn maximum_matching(&mut self) -> Vec<(usize, usize)> {
38 self.compute();
39 let mut res = Vec::with_capacity(self.matching_size);
40 for v in 0..self.size {
41 let u = self.mate[v];
42 if u != !0 && v < u {
43 res.push((v, u));
44 }
45 }
46 res
47 }
48 fn compute(&mut self) {
49 if self.matching_size != !0 {
50 return;
51 }
52 let mut cnt = 0usize;
53 for &m in &self.mate {
54 if m != !0 {
55 cnt += 1;
56 }
57 }
58 self.matching_size = cnt / 2;
59
60 let mut p = vec![!0; self.size];
61 for v in 0..self.size {
62 if self.mate[v] == !0 {
63 let finish = self.find_path(v, &mut p);
64 if finish != !0 {
65 self.augment(finish, &p);
66 self.matching_size += 1;
67 }
68 }
69 }
70 }
71 fn augment(&mut self, mut v: usize, p: &[usize]) {
72 while v != !0 {
73 let pv = p[v];
74 let nv = if pv != !0 { self.mate[pv] } else { !0 };
75 self.mate[v] = pv;
76 if pv != !0 {
77 self.mate[pv] = v;
78 }
79 v = nv;
80 }
81 }
82 fn find_path(&self, root: usize, p: &mut [usize]) -> usize {
83 let n = self.size;
84 p.fill(!0);
85 let mut used = vec![false; n];
86 let mut base: Vec<usize> = (0..n).collect();
87 let mut q = VecDeque::with_capacity(n);
88 let mut lca_vis = vec![0usize; n];
89 let mut lca_iter = 0usize;
90
91 used[root] = true;
92 q.push_back(root);
93 while let Some(v) = q.pop_front() {
94 for &u in &self.graph[v] {
95 if base[v] == base[u] || self.mate[v] == u {
96 continue;
97 }
98 if u == root || (self.mate[u] != !0 && p[self.mate[u]] != !0) {
99 let cur = {
100 let mut a = v;
101 let mut b = u;
102 lca_iter += 1;
103 let iter = lca_iter;
104 loop {
105 a = base[a];
106 lca_vis[a] = iter;
107 if self.mate[a] == !0 {
108 break;
109 }
110 a = p[self.mate[a]];
111 }
112 loop {
113 b = base[b];
114 if lca_vis[b] == iter {
115 break b;
116 }
117 if self.mate[b] == !0 {
118 break b;
119 }
120 b = p[self.mate[b]];
121 }
122 };
123 let mut blossom = vec![false; n];
124 mark_path(&self.mate, &base, p, &mut blossom, v, cur, u);
125 mark_path(&self.mate, &base, p, &mut blossom, u, cur, v);
126 for i in 0..n {
127 if blossom[base[i]] {
128 base[i] = cur;
129 if !used[i] {
130 used[i] = true;
131 q.push_back(i);
132 }
133 }
134 }
135 } else if p[u] == !0 {
136 p[u] = v;
137 if self.mate[u] == !0 {
138 return u;
139 }
140 let m = self.mate[u];
141 used[m] = true;
142 q.push_back(m);
143 }
144 }
145 }
146 !0
147 }
148}
149
150fn mark_path(
151 mate: &[usize],
152 base: &[usize],
153 p: &mut [usize],
154 blossom: &mut [bool],
155 mut v: usize,
156 b: usize,
157 mut child: usize,
158) {
159 while base[v] != b {
160 blossom[base[v]] = true;
161 blossom[base[mate[v]]] = true;
162 p[v] = child;
163 child = mate[v];
164 v = p[mate[v]];
165 }
166}
167
168#[cfg(test)]
169mod tests {
170 use super::*;
171 use crate::{rand, tools::Xorshift};
172
173 fn brute_maximum_matching(n: usize, edges: &[(usize, usize)]) -> usize {
174 let mut adj = vec![vec![false; n]; n];
175 for &(u, v) in edges {
176 adj[u][v] = true;
177 adj[v][u] = true;
178 }
179 let mut dp = vec![0usize; 1 << n];
180 for mask in 1usize..1 << n {
181 let i = mask.trailing_zeros() as usize;
182 let mask_without_i = mask & !(1 << i);
183 let mut best = dp[mask_without_i];
184 let mut m = mask_without_i;
185 while m != 0 {
186 let j = m.trailing_zeros() as usize;
187 if adj[i][j] {
188 let val = 1 + dp[mask_without_i & !(1 << j)];
189 if val > best {
190 best = val;
191 }
192 }
193 m &= m - 1;
194 }
195 dp[mask] = best;
196 }
197 dp[(1 << n) - 1]
198 }
199
200 #[test]
201 fn test_general_matching() {
202 const Q: usize = 200;
203 const N: usize = 10;
204 let mut rng = Xorshift::default();
205 for _ in 0..Q {
206 rand!(rng, n: 1..=N);
207 let mut edges = vec![];
208 for i in 0..n {
209 for j in i + 1..n {
210 rand!(rng, b: 0..2usize);
211 if b == 1 {
212 edges.push((i, j));
213 }
214 }
215 }
216 let mut gm = GeneralMatching::from_edges(n, &edges);
217 let matching = gm.maximum_matching();
218 let mut used = vec![false; n];
219 let mut adj = vec![vec![false; n]; n];
220 for &(u, v) in &edges {
221 adj[u][v] = true;
222 adj[v][u] = true;
223 }
224 for &(u, v) in &matching {
225 assert!(u < v);
226 assert!(adj[u][v]);
227 assert!(!used[u]);
228 assert!(!used[v]);
229 used[u] = true;
230 used[v] = true;
231 }
232 assert_eq!(matching.len(), brute_maximum_matching(n, &edges));
233 }
234 }
235}