dsalgo/
maximum_cardinality_matching.rs

1pub 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    } // v \in A, u \in B.
127    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() {}
dsalgo/maximum_cardinality_matching.rs

dsalgo/
maximum_cardinality_matching.rs
