Struct GeneralMatching

Source

pub struct GeneralMatching {
    size: usize,
    graph: Vec<Vec<usize>>,
    mate: Vec<usize>,
    matching_size: usize,
    parent: Vec<usize>,
    base: Vec<usize>,
    state: Vec<u8>,
    seen: Vec<usize>,
    queue: Vec<usize>,
    timestamp: usize,
}

Fields§

§size: usize§graph: Vec<Vec<usize>>§mate: Vec<usize>§matching_size: usize§parent: Vec<usize>§base: Vec<usize>§state: Vec<u8>§seen: Vec<usize>§queue: Vec<usize>§timestamp: usize

Implementations§

Source §

pub fn new(size: usize) -> Self

Examples found in repository ?

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

42    pub fn from_edges(size: usize, edges: &[(usize, usize)]) -> Self {
43        let mut this = Self::new(size);
44        for &(u, v) in edges {
45            this.add_edge(u, v);
46        }
47        this
48    }

More examples

Hide additional examples

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

5pub fn general_matching(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, uv: [(usize, usize); iter m]);
8    let mut gm = GeneralMatching::new(n);
9    for (u, v) in uv {
10        gm.add_edge(u, v);
11    }
12    let matching = gm.maximum_matching();
13    pp!(matching.len(); @ittup matching);
14}

Source

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

Examples found in repository ?

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

42    pub fn from_edges(size: usize, edges: &[(usize, usize)]) -> Self {
43        let mut this = Self::new(size);
44        for &(u, v) in edges {
45            this.add_edge(u, v);
46        }
47        this
48    }

More examples

Hide additional examples

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

5pub fn general_matching(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, uv: [(usize, usize); iter m]);
8    let mut gm = GeneralMatching::new(n);
9    for (u, v) in uv {
10        gm.add_edge(u, v);
11    }
12    let matching = gm.maximum_matching();
13    pp!(matching.len(); @ittup matching);
14}

Source

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

Source

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

Examples found in repository ?

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

5pub fn general_matching(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, uv: [(usize, usize); iter m]);
8    let mut gm = GeneralMatching::new(n);
9    for (u, v) in uv {
10        gm.add_edge(u, v);
11    }
12    let matching = gm.maximum_matching();
13    pp!(matching.len(); @ittup matching);
14}

Source

fn compute(&mut self)

Examples found in repository ?

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

49    pub fn maximum_matching(&mut self) -> Vec<(usize, usize)> {
50        self.compute();
51        let mut res = Vec::with_capacity(self.matching_size);
52        for v in 0..self.size {
53            let u = self.mate[v];
54            if u != self.size && v < u {
55                res.push((v, u));
56            }
57        }
58        res
59    }

Source

fn find(&mut self, v: usize) -> usize

Examples found in repository ?

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

86    fn lca(&mut self, mut u: usize, mut v: usize) -> usize {
87        self.timestamp += 1;
88        u = self.find(u);
89        v = self.find(v);
90        loop {
91            if u != self.size {
92                if self.seen[u] == self.timestamp {
93                    return u;
94                }
95                self.seen[u] = self.timestamp;
96                u = self.find(self.parent[self.mate[u]]);
97            }
98            swap(&mut u, &mut v);
99        }
100    }
101
102    fn contract(&mut self, mut v: usize, mut child: usize, ancestor: usize) {
103        while self.find(v) != ancestor {
104            self.parent[v] = child;
105            child = self.mate[v];
106            if self.state[child] == Self::INNER {
107                self.state[child] = Self::OUTER;
108                self.queue.push(child);
109            }
110            if self.base[v] == v {
111                self.base[v] = ancestor;
112            }
113            if self.base[child] == child {
114                self.base[child] = ancestor;
115            }
116            v = self.parent[child];
117        }
118    }
119
120    fn augment_from(&mut self, root: usize) -> bool {
121        for (v, base) in self.base.iter_mut().enumerate() {
122            *base = v;
123        }
124        self.state.fill(Self::UNSEEN);
125        self.queue.clear();
126        self.state[root] = Self::OUTER;
127        self.queue.push(root);
128        let mut head = 0;
129        while head < self.queue.len() {
130            let u = self.queue[head];
131            head += 1;
132            for edge in 0..self.graph[u].len() {
133                let v = self.graph[u][edge];
134                if self.state[v] == Self::UNSEEN {
135                    self.parent[v] = u;
136                    self.state[v] = Self::INNER;
137                    if self.mate[v] == self.size {
138                        let mut v = v;
139                        let mut u = u;
140                        while u != self.size {
141                            let next = self.mate[u];
142                            self.mate[u] = v;
143                            self.mate[v] = u;
144                            v = next;
145                            u = self.parent[v];
146                        }
147                        return true;
148                    }
149                    let v = self.mate[v];
150                    self.state[v] = Self::OUTER;
151                    self.queue.push(v);
152                } else if self.state[v] == Self::OUTER && self.find(u) != self.find(v) {
153                    let ancestor = self.lca(u, v);
154                    self.contract(u, v, ancestor);
155                    self.contract(v, u, ancestor);
156                }
157            }
158        }
159        false
160    }

Source

fn lca(&mut self, u: usize, v: usize) -> usize

Examples found in repository ?

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

120    fn augment_from(&mut self, root: usize) -> bool {
121        for (v, base) in self.base.iter_mut().enumerate() {
122            *base = v;
123        }
124        self.state.fill(Self::UNSEEN);
125        self.queue.clear();
126        self.state[root] = Self::OUTER;
127        self.queue.push(root);
128        let mut head = 0;
129        while head < self.queue.len() {
130            let u = self.queue[head];
131            head += 1;
132            for edge in 0..self.graph[u].len() {
133                let v = self.graph[u][edge];
134                if self.state[v] == Self::UNSEEN {
135                    self.parent[v] = u;
136                    self.state[v] = Self::INNER;
137                    if self.mate[v] == self.size {
138                        let mut v = v;
139                        let mut u = u;
140                        while u != self.size {
141                            let next = self.mate[u];
142                            self.mate[u] = v;
143                            self.mate[v] = u;
144                            v = next;
145                            u = self.parent[v];
146                        }
147                        return true;
148                    }
149                    let v = self.mate[v];
150                    self.state[v] = Self::OUTER;
151                    self.queue.push(v);
152                } else if self.state[v] == Self::OUTER && self.find(u) != self.find(v) {
153                    let ancestor = self.lca(u, v);
154                    self.contract(u, v, ancestor);
155                    self.contract(v, u, ancestor);
156                }
157            }
158        }
159        false
160    }

Source

fn contract(&mut self, v: usize, child: usize, ancestor: usize)

Examples found in repository ?

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

120    fn augment_from(&mut self, root: usize) -> bool {
121        for (v, base) in self.base.iter_mut().enumerate() {
122            *base = v;
123        }
124        self.state.fill(Self::UNSEEN);
125        self.queue.clear();
126        self.state[root] = Self::OUTER;
127        self.queue.push(root);
128        let mut head = 0;
129        while head < self.queue.len() {
130            let u = self.queue[head];
131            head += 1;
132            for edge in 0..self.graph[u].len() {
133                let v = self.graph[u][edge];
134                if self.state[v] == Self::UNSEEN {
135                    self.parent[v] = u;
136                    self.state[v] = Self::INNER;
137                    if self.mate[v] == self.size {
138                        let mut v = v;
139                        let mut u = u;
140                        while u != self.size {
141                            let next = self.mate[u];
142                            self.mate[u] = v;
143                            self.mate[v] = u;
144                            v = next;
145                            u = self.parent[v];
146                        }
147                        return true;
148                    }
149                    let v = self.mate[v];
150                    self.state[v] = Self::OUTER;
151                    self.queue.push(v);
152                } else if self.state[v] == Self::OUTER && self.find(u) != self.find(v) {
153                    let ancestor = self.lca(u, v);
154                    self.contract(u, v, ancestor);
155                    self.contract(v, u, ancestor);
156                }
157            }
158        }
159        false
160    }

Source

fn augment_from(&mut self, root: usize) -> bool

Examples found in repository ?

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

60    fn compute(&mut self) {
61        if self.matching_size != !0 {
62            return;
63        }
64        self.matching_size = self.mate.iter().filter(|&&mate| mate != self.size).count() / 2;
65
66        for v in 0..self.size {
67            if self.mate[v] == self.size && self.augment_from(v) {
68                self.matching_size += 1;
69            }
70        }
71    }