dsalgo/
maximum_cardinality_matching.rs1pub fn ford_fulkerson(
2 size_a: usize,
3 size_b: usize,
4 g: &[(usize, usize)],
5) -> Vec<Option<usize>> {
6 fn dfs(
7 g: &[Vec<usize>],
8 pair: &mut [Option<usize>],
9 visited: &mut [bool],
10 u: usize,
11 ) -> bool {
12 visited[u] = true;
13
14 for &v in g[u].iter() {
15 if !pair[v]
16 .map_or(true, |v| !visited[v] && dfs(g, pair, visited, v))
17 {
18 continue;
19 }
20
21 pair[v] = Some(u);
22
23 pair[u] = Some(v);
24
25 return true;
26 }
27
28 false
29 }
30
31 let n = size_a + size_b;
32
33 let mut t = vec![vec![]; n];
34
35 for &(u, v) in g.iter() {
36 t[u].push(v + size_a);
37
38 t[v + size_a].push(u);
39 }
40
41 let mut pair = vec![None; n];
42
43 for i in 0..size_a {
44 if pair[i].is_some() {
45 continue;
46 }
47
48 dfs(&t, &mut pair, &mut vec![false; n], i);
49 }
50
51 pair.into_iter().take(size_a).collect()
52}
53
54pub fn hopcroft_karp(
55 size_a: usize,
56 size_b: usize,
57 g: &[(usize, usize)],
58) -> Vec<Option<usize>> {
59 let bfs = |g: &[Vec<usize>],
60 matched: &[bool],
61 pair_a: &[Option<usize>]|
62 -> Vec<usize> {
63 let mut que = std::collections::VecDeque::new();
64
65 let mut level = vec![std::usize::MAX; size_b];
66
67 for u in 0..size_b {
68 if matched[u] {
69 continue;
70 }
71
72 level[u] = 0;
73
74 que.push_back(u);
75 }
76
77 while let Some(u) = que.pop_front() {
78 for &v in g[u].iter() {
79 if let Some(u2) = pair_a[v] {
80 if level[u2] <= level[u] + 1 {
81 continue;
82 }
83
84 level[u2] = level[u] + 1;
85
86 que.push_back(u2);
87 }
88 }
89 }
90
91 level
92 };
93
94 fn dfs(
95 g: &[Vec<usize>],
96 level: &[usize],
97 it: &mut [usize],
98 pair_a: &mut [Option<usize>],
99 matched: &mut [bool],
100 u: usize,
101 ) -> bool {
102 for (i, &v) in g[u].iter().enumerate().skip(it[u]) {
103 it[u] = i + 1;
104
105 if !pair_a[v].map_or(true, |u2| {
106 level[u2] == level[u] + 1
107 && dfs(g, level, it, pair_a, matched, u2)
108 }) {
109 continue;
110 }
111
112 pair_a[v] = Some(u);
113
114 matched[u] = true;
115
116 return true;
117 }
118
119 false
120 }
121
122 let mut t = vec![vec![]; size_b];
123
124 for &(v, u) in g.iter() {
125 t[u].push(v);
126 } let mut matched = vec![false; size_b];
128
129 let mut pair_a = vec![None; size_a];
130
131 loop {
132 let level = bfs(&t, &matched, &pair_a);
133
134 let mut it = vec![0; size_b];
135
136 let mut updated = false;
137
138 for u in 0..size_b {
139 if !matched[u] {
140 updated |=
141 dfs(&t, &level, &mut it, &mut pair_a, &mut matched, u);
142 }
143 }
144
145 if !updated {
146 break;
147 }
148 }
149
150 pair_a
151}
152
153pub fn blossom() {}