Struct HopcroftKarp

pub struct HopcroftKarp { /* private fields */ }

Hopcroft-Karp法によって、最大二部マッチングを求める。

Implementations

impl HopcroftKarp

pub fn new(left: usize, right: usize) -> Self

左側の頂点数がleft、右側の頂点数がrightの空の二部グラフを用意する。

pub fn add_edge(&mut self, i: usize, j: usize)

左側iと右側jに辺を張る。

pub fn matching(&mut self) -> Vec<(usize, usize)>

最大マッチングの辺集合を返す。