» » Bipartite Matching (Basic)

Bipartite Matching (Basic)

   7:16 PM       

 
#define mx 210
vector < int > g[mx];
int lf[mx],rt[mx],n;
bool vis[mx];

bool dfs(int p) {
 int i,j=g[p].size();
 for(i=0;i<j;i++) if(!vis[g[p][i]]) {
  vis[g[p][i]]=1;
  if(rt[g[p][i]]==-1 || dfs(rt[g[p][i]])) {
   rt[g[p][i]]=p;
   lf[p]=g[p][i];
   return true;
  }
 }
 return false;
}

int bpm() {
 int i,q=0;
 memset(lf,-1,sizeof lf);
 memset(rt,-1,sizeof rt);
 
 for(i=0;i<n;i++) {
  memset(vis,0,sizeof vis);
  if(dfs(i))q++;
 }
 return q;
}