haar_lib/matching/
hopcroft_karp.rs

1//! 二部マッチング (Hopcroft-Karp)
2
3use std::collections::VecDeque;
4
5/// Hopcroft-Karp法によって、最大二部マッチングを求める。
6pub struct HopcroftKarp {
7    left: usize,
8    right: usize,
9    edges: Vec<Vec<usize>>,
10    pair_left: Vec<usize>,
11    pair_right: Vec<usize>,
12    dist: Vec<usize>,
13}
14
15const INF: usize = usize::MAX;
16
17impl HopcroftKarp {
18    /// 左側の頂点数が`left`、右側の頂点数が`right`の空の二部グラフを用意する。
19    pub fn new(left: usize, right: usize) -> Self {
20        Self {
21            left,
22            right,
23            edges: vec![vec![]; left + 1],
24            pair_left: vec![0; left + 1],
25            pair_right: vec![0; right + 1],
26            dist: vec![INF; left + 1],
27        }
28    }
29
30    /// 左側`i`と右側`j`に辺を張る。
31    pub fn add_edge(&mut self, i: usize, j: usize) {
32        assert!(i < self.left);
33        assert!(j < self.right);
34        self.edges[i + 1].push(j + 1);
35    }
36
37    fn bfs(&mut self) -> bool {
38        let mut q = VecDeque::new();
39
40        self.dist.fill(INF);
41        for l in 1..=self.left {
42            if self.pair_left[l] == 0 {
43                q.push_back(l);
44                self.dist[l] = 0;
45            }
46        }
47
48        while let Some(l) = q.pop_front() {
49            if self.dist[l] < self.dist[0] {
50                for &r in &self.edges[l] {
51                    let t = self.pair_right[r];
52                    if self.dist[t] == INF {
53                        self.dist[t] = self.dist[l] + 1;
54                        q.push_back(t);
55                    }
56                }
57            }
58        }
59
60        self.dist[0] != INF
61    }
62
63    fn dfs(&mut self, cur: usize) -> bool {
64        if cur != 0 {
65            let l = cur;
66            for i in 0..self.edges[l].len() {
67                let r = self.edges[l][i];
68
69                if self.dist[self.pair_right[r]] == self.dist[l] + 1 && self.dfs(self.pair_right[r])
70                {
71                    self.pair_right[r] = l;
72                    self.pair_left[l] = r;
73                    return true;
74                }
75            }
76
77            self.dist[cur] = INF;
78            return false;
79        }
80
81        true
82    }
83
84    /// 最大マッチングの辺集合を返す。
85    pub fn matching(&mut self) -> Vec<(usize, usize)> {
86        while self.bfs() {
87            for l in 1..=self.left {
88                if self.pair_left[l] == 0 {
89                    self.dfs(l);
90                }
91            }
92        }
93
94        (1..=self.left)
95            .filter_map(|l| {
96                let r = self.pair_left[l];
97                (r != 0).then(|| (l - 1, r - 1))
98            })
99            .collect()
100    }
101}
haar_lib/matching/hopcroft_karp.rs

haar_lib/matching/
hopcroft_karp.rs
