二分图

整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。

难度为阅读建议，可从 ACM 学习索引 按阶段阅读。

---

染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图

时间复杂度是 $O(n+m)$, $n$ 表示点数，$m$ 表示边数

bool dfs(int u,int c){//判断存在奇环，存在返回true
  color[u]=c;
  for(auto v:e[u]){
   
    if(!color[v]){
      if(dfs(v,3-c))return 1;
    }
    else if(color[v]==c)return 1;//有奇环
  }
  return 0;
}
bool check()
{//判断是不是二分图
    fill(color,color+1+n,0);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )//可能图不连通
        if (!color[i] )
            if (dfs(i, 1))//有奇环就不是二分图
            {
                flag = false;
                break;
            }
    return flag;
}

---

匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配

时间复杂度是 $O(nm)$, $n$ 表示点数，$m$ 表示边数

int ans=0;
vector<int>e[N];
int vis[N],match[N];
bool dfs(int u){
  for(auto v:e[u]){
    //妹子的编号v
    if(vis[v]) continue;
    vis[v]=1; //先标记这个妹子
    if(!match[v]||dfs(match[v])){
      match[v]=u; //配成对
      return 1;
    }
  }
  return 0;
}
void solve(){
	int k;
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		fill(vis,vis+m+1,0);//每轮找增广路以前清空vis
		if(dfs(i))ans++;
	}
	cout<<ans;
}