fn mark_path(
mate: &[usize],
base: &[usize],
p: &mut [usize],
blossom: &mut [bool],
v: usize,
b: usize,
child: usize,
)Examples found in repository?
crates/competitive/src/graph/general_matching.rs (line 124)
82 fn find_path(&self, root: usize, p: &mut [usize]) -> usize {
83 let n = self.size;
84 p.fill(!0);
85 let mut used = vec![false; n];
86 let mut base: Vec<usize> = (0..n).collect();
87 let mut q = VecDeque::with_capacity(n);
88 let mut lca_vis = vec![0usize; n];
89 let mut lca_iter = 0usize;
90
91 used[root] = true;
92 q.push_back(root);
93 while let Some(v) = q.pop_front() {
94 for &u in &self.graph[v] {
95 if base[v] == base[u] || self.mate[v] == u {
96 continue;
97 }
98 if u == root || (self.mate[u] != !0 && p[self.mate[u]] != !0) {
99 let cur = {
100 let mut a = v;
101 let mut b = u;
102 lca_iter += 1;
103 let iter = lca_iter;
104 loop {
105 a = base[a];
106 lca_vis[a] = iter;
107 if self.mate[a] == !0 {
108 break;
109 }
110 a = p[self.mate[a]];
111 }
112 loop {
113 b = base[b];
114 if lca_vis[b] == iter {
115 break b;
116 }
117 if self.mate[b] == !0 {
118 break b;
119 }
120 b = p[self.mate[b]];
121 }
122 };
123 let mut blossom = vec![false; n];
124 mark_path(&self.mate, &base, p, &mut blossom, v, cur, u);
125 mark_path(&self.mate, &base, p, &mut blossom, u, cur, v);
126 for i in 0..n {
127 if blossom[base[i]] {
128 base[i] = cur;
129 if !used[i] {
130 used[i] = true;
131 q.push_back(i);
132 }
133 }
134 }
135 } else if p[u] == !0 {
136 p[u] = v;
137 if self.mate[u] == !0 {
138 return u;
139 }
140 let m = self.mate[u];
141 used[m] = true;
142 q.push_back(m);
143 }
144 }
145 }
146 !0
147 }