Struct GeneralMatching

Source

pub struct GeneralMatching {
    size: usize,
    graph: Vec<Vec<usize>>,
    mate: Vec<usize>,
    matching_size: usize,
}

Fields§

§size: usize§graph: Vec<Vec<usize>>§mate: Vec<usize>§matching_size: usize

Implementations§

Source §

impl GeneralMatching

Source

pub fn new(size: usize) -> Self

Examples found in repository ?

crates/competitive/src/graph/general_matching.rs (line 31)

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    }

Source

pub fn add_edge(&mut self, u: usize, v: usize)

Examples found in repository ?

crates/competitive/src/graph/general_matching.rs (line 33)

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    }

Source

pub fn from_edges(size: usize, edges: &[(usize, usize)]) -> Self

Examples found in repository ?

crates/library_checker/src/graph/general_matching.rs (line 10)

6pub fn general_matching(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, uv: [(usize, usize); m]);
10    let mut gm = GeneralMatching::from_edges(n, &uv);
11    let matching = gm.maximum_matching();
12    writeln!(writer, "{}", matching.len()).ok();
13    for (u, v) in matching {
14        writeln!(writer, "{} {}", u, v).ok();
15    }
16}

Source

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

Examples found in repository ?

crates/library_checker/src/graph/general_matching.rs (line 11)

6pub fn general_matching(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, uv: [(usize, usize); m]);
10    let mut gm = GeneralMatching::from_edges(n, &uv);
11    let matching = gm.maximum_matching();
12    writeln!(writer, "{}", matching.len()).ok();
13    for (u, v) in matching {
14        writeln!(writer, "{} {}", u, v).ok();
15    }
16}

Source

fn compute(&mut self)

Examples found in repository ?

crates/competitive/src/graph/general_matching.rs (line 38)

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    }

Source

fn augment(&mut self, v: usize, p: &[usize])

Examples found in repository ?

crates/competitive/src/graph/general_matching.rs (line 65)

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    }

Source

fn find_path(&self, root: usize, p: &mut [usize]) -> usize

Examples found in repository ?

crates/competitive/src/graph/general_matching.rs (line 63)

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    }