// codesnip-guard: regular_bipartite_edge_coloring
#[cfg_attr(any(),rustfmt::skip)]pub use self::regular_bipartite_edge_coloring::regular_bipartite_edge_coloring;#[cfg_attr(any(),rustfmt::skip)]mod regular_bipartite_edge_coloring{use super::BipartiteMatching;#[doc=" Colors in `0..degree`, in edge order; `None` if nonregular. Each part has `size` vertices."]pub fn regular_bipartite_edge_coloring(size:usize,edges:&[(usize,usize)])->Option<Vec<usize>>{let mut left_degree=vec![0;size];let mut right_degree=vec![0;size];for&(l,r)in edges{left_degree[l]+=1;right_degree[r]+=1;}let degree=left_degree.first().copied().unwrap_or(0);if left_degree.iter().chain(&right_degree).any(|&d|d!=degree){return None;}let mut colors=vec![!0;edges.len()];let mut remaining:Vec<_>=(0..edges.len()).collect();let mut selected=vec![!0;size];for color in 0..degree{let mut matching=BipartiteMatching::new(size,size);for&eid in&remaining{let(l,r)=edges[eid];matching.add_edge(l,r);}for(l,r)in matching.maximum_matching(){selected[l]=r;}remaining.retain(|&eid|{let(l,r)=edges[eid];if selected[l]==r{colors[eid]=color;selected[l]=!0;false}else{true}});}Some(colors)}}
// codesnip-guard: BipartiteMatching
#[cfg_attr(any(),rustfmt::skip)]pub use self::bipartite_matching::BipartiteMatching;#[cfg_attr(any(),rustfmt::skip)]mod bipartite_matching{use std::{collections::VecDeque,mem::swap};#[derive(Debug,Clone)]pub struct BipartiteMatching{left_size:usize,right_size:usize,left_graph:Vec<Vec<usize>>,right_graph:Vec<Vec<usize>>,left_match:Vec<Option<usize>>,right_match:Vec<Option<usize>>,matching_size:usize}impl BipartiteMatching{pub fn new(left_size:usize,right_size:usize)->Self{Self{left_size,right_size,left_graph:vec![vec![];left_size],right_graph:vec![vec![];right_size],left_match:vec![None;left_size],right_match:vec![None;right_size],matching_size:0}}pub fn add_edge(&mut self,l:usize,r:usize){assert!(l<self.left_size);assert!(r<self.right_size);self.left_graph[l].push(r);self.right_graph[r].push(l);self.matching_size=!0;}pub fn from_edges(left_size:usize,right_size:usize,lr:&[(usize,usize)])->Self{let mut left_deg=vec![0usize;left_size];let mut right_deg=vec![0usize;right_size];for&(l,r)in lr{left_deg[l]+=1;right_deg[r]+=1;}let mut left_graph:Vec<_>=left_deg.into_iter().map(Vec::with_capacity).collect();let mut right_graph:Vec<_>=right_deg.into_iter().map(Vec::with_capacity).collect();for&(l,r)in lr{assert!(l<left_size);assert!(r<right_size);left_graph[l].push(r);right_graph[r].push(l);}Self{left_size,right_size,left_graph,right_graph,left_match:vec![None;left_size],right_match:vec![None;right_size],matching_size:!0}}pub fn hopcroft_karp(&mut self){fn bfs(bm:&BipartiteMatching,deq:&mut VecDeque<usize>,level:&mut[usize]){deq.clear();for(i,r)in bm.left_match.iter().enumerate(){if r.is_none(){deq.push_back(i);level[i]=0;}}while let Some(l)=deq.pop_front(){for&r in&bm.left_graph[l]{if let Some(nl)=bm.right_match[r]&&level[nl]==!0{deq.push_back(nl);level[nl]=level[l]+1;}}}}fn dfs(bm:&mut BipartiteMatching,l:usize,level:&mut[usize],used:&mut[bool])->bool{used[l]=true;for i in 0..bm.left_graph[l].len(){let r=bm.left_graph[l][i];if let Some(nl)=bm.right_match[r]&&(used[nl]||level[l]+1!=level[nl]||!dfs(bm,nl,level,used)){continue;}bm.right_match[r]=Some(l);bm.left_match[l]=Some(r);return true;}false}if self.matching_size!=!0{return;}self.matching_size=self.left_match.iter().filter(|r|r.is_some()).count();let mut used=vec![false;self.left_size];let mut level=vec![!0;self.left_size];let mut deq=VecDeque::with_capacity(self.left_size);loop{bfs(self,&mut deq,&mut level);let prev_size=self.matching_size;for l in 0..self.left_size{if self.left_match[l].is_none(){self.matching_size+=dfs(self,l,&mut level,&mut used)as usize;}}if self.matching_size==prev_size{break;}for item in level.iter_mut(){*item=!0;}for item in used.iter_mut(){*item=false;}}}pub fn kuhn_multi_start_bfs(&mut self){if self.matching_size!=!0{return;}self.matching_size=self.left_match.iter().filter(|r|r.is_some()).count();let mut deq=VecDeque::with_capacity(self.left_size);let mut prev=vec![!0usize;self.left_size];let mut root=vec![!0usize;self.left_size];loop{let mut changed=false;for(l,r)in self.left_match.iter().enumerate(){if r.is_none(){root[l]=l;deq.push_back(l);}}while let Some(mut l)=deq.pop_front(){if self.left_match[root[l]].is_some(){continue;}for mut r in self.left_graph[l].iter().cloned(){if let Some(nl)=self.right_match[r]{if prev[nl]==!0{prev[nl]=l;root[nl]=root[l];deq.push_back(nl);}}else{loop{self.right_match[r]=Some(l);if let Some(nr)=&mut self.left_match[l]{swap(nr,&mut r);l=prev[l];}else{self.left_match[l]=Some(r);break;}}changed=true;self.matching_size+=1;break;}}}if!changed{break;}for item in prev.iter_mut(){*item=!0;}for item in root.iter_mut(){*item=!0;}}}pub fn push_relabel(&mut self){if self.matching_size!=!0{return;}let size=self.left_size+self.right_size;let mut level_left=vec![size;self.left_size];let mut level_right=vec![size;self.right_size];let mut bfs=VecDeque::with_capacity(self.left_size);let mut queue:VecDeque<_>=self.right_match.iter().enumerate().filter_map(|(right,left)|left.is_none().then_some(right)).collect();let mut iteration=0;while let Some(right)=queue.pop_front(){if iteration==0{level_left.fill(size);level_right.fill(size);bfs.clear();for(left,right)in self.left_match.iter().enumerate(){if right.is_none(){level_left[left]=0;bfs.push_back(left);}}while let Some(left)=bfs.pop_front(){for&right in&self.left_graph[left]{if level_right[right]>level_left[left]+1{level_right[right]=level_left[left]+1;if let Some(next_left)=self.right_match[right]{level_left[next_left]=level_right[right]+1;bfs.push_back(next_left);}}}}}let mut selected=!0;let mut selected_level=size;for&left in&self.right_graph[right]{if level_left[left]<selected_level{selected=left;selected_level=level_left[left];}}if selected!=!0{level_right[right]=selected_level+1;if let Some(previous_right)=self.left_match[selected].take(){self.right_match[previous_right]=None;queue.push_back(previous_right);}self.left_match[selected]=Some(right);self.right_match[right]=Some(selected);level_left[selected]+=2;}iteration+=1;if iteration==size{iteration=0;}}self.matching_size=self.left_match.iter().filter(|right|right.is_some()).count();}pub fn maximum_matching(&mut self)->Vec<(usize,usize)>{self.push_relabel();self.left_match.iter().enumerate().filter_map(|(l,r)|r.map(|r|(l,r))).collect()}pub fn minimum_edge_cover(&mut self)->Vec<(usize,usize)>{self.push_relabel();let mut res=Vec::with_capacity(self.left_size+self.right_size-self.matching_size);let mut left_used:Vec<_>=self.left_match.iter().map(Option::is_some).collect();let mut right_used:Vec<_>=self.right_match.iter().map(Option::is_some).collect();for(l,lg)in self.left_graph.iter().enumerate(){if let Some(r)=self.left_match[l]{res.push((l,r));}for&r in lg{if!left_used[l]||!right_used[r]{left_used[l]=true;right_used[r]=true;res.push((l,r));}}}res}fn reachable(&mut self)->(Vec<bool>,Vec<bool>){#[derive(Clone,Copy)]enum Either{Left(usize),Right(usize)}self.push_relabel();let mut left_used=vec![false;self.left_size];let mut right_used=vec![false;self.right_size];let mut deq=VecDeque::new();for(l,r)in self.left_match.iter().enumerate(){if r.is_none(){left_used[l]=true;deq.push_back(Either::Left(l));}}loop{match deq.pop_front(){Some(Either::Left(l))=>{for&r in&self.left_graph[l]{if self.left_match[l]!=Some(r)&&!right_used[r]{right_used[r]=true;deq.push_back(Either::Right(r));}}}Some(Either::Right(r))=>{if let Some(l)=self.right_match[r]&&!left_used[l]{left_used[l]=true;deq.push_back(Either::Left(l));}}None=>break,}}(left_used,right_used)}pub fn minimum_vertex_cover(&mut self)->(Vec<usize>,Vec<usize>){let(left_used,right_used)=self.reachable();(left_used.into_iter().enumerate().filter_map(|(l,b)|if!b{Some(l)}else{None}).collect(),right_used.into_iter().enumerate().filter_map(|(r,b)|if b{Some(r)}else{None}).collect())}pub fn maximum_independent_set(&mut self)->(Vec<usize>,Vec<usize>){let(left_used,right_used)=self.reachable();(left_used.into_iter().enumerate().filter_map(|(l,b)|if b{Some(l)}else{None}).collect(),right_used.into_iter().enumerate().filter_map(|(r,b)|if!b{Some(r)}else{None}).collect())}}}