二分图相关模板

#include<iostream>
using namespace std;
int n,m,k;
int map[MAXN][MAXN];//存储二分图的关系
int link[MAXN],used[MAXN];//link=-1是未连接，used代表是否用过
int dfs(int x) {
  for(int i=1; i<=m; i++) {//注意此处的m，右部的大小，map[][m] 
    if(map[x][i] && ! used[i]) {
      used[i]=1;
      if(link[i]==-1 || dfs(link[i])) {
        link[i]=x;
        return 1;
      }
    }
  }
  return 0;
}
void work() {
  int sum=0;
  for(int i=1; i<=n; i++) {//注意此处n，左部的大小，map[n][] 
    memset(used,0,sizeof(used));//每次都要把used置空
    if(dfs(i)) {
      sum++;
    }
  }
  cout<<sum<<endl;//注意如果存无向图，可能要除以二，自己注意
}
int main() {
  memset(link,-1,sizeof(link));
  memset(map,0,sizeof(map));
}

#include<iostream>
#include<queue>
using namespace std;
int n,m,k;
vector<int>e[MAXN];//用vector存图
int color[MAXN];
bool bfs(int s) {//上色代码 
  queue<int> q;
  q.push(s);
  color[s]=1;//上色 1 
  while(!q.empty()) {
    int now=q.front();
    q.pop();
    for(int i=0; i<e[now].size(); i++) {//遍历与之相连的点 
      int v=e[now][i];
      if(color[v]==-1) {//如果没上过色，上色为！1，也就是0，未上色是-1 
        color[v]=!color[now];
        q.push(v);
      }
      if(color[v]==color[now]) {
        return 0;
      }
    }
  }
  return 1;
}
bool dfs(int u) {//最大匹配代码 
  for(int i=0; i<e[u].size(); i++) {
    int v=e[u][i];
    if(!vis[v]) {
      vis[v]=1;
      if(match[v]==0||dfs(match[v])) {
        match[v]=u;
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  for(int i=0; i<MAXN; i++) {
    e[i].clear();
  }
  memset(color,-1,sizeof(color));
}