二分图的判定
(参见算法竞赛进阶指南)

定理

一张图是无向图,当且仅当图中不存在奇环

如何判断一张图为无向图

对于每个点,进行染色,相邻的点不同染成不同颜色,当发现出现矛盾时则不是二分图。时间复杂度为O(N+M)O(N + M)

二分图最大匹配

匈牙利算法

算法思路:用dfs进行增广,对于每个xx,每次增广寻找一个相匹配点yy。出现下列两种情况

  1. yy未被匹配时

    只需将xx匹配给yy即可,并进行记录

  2. yy已被匹配时

    假设yyxx'已匹配,那么递归调用到xx'并进行尝试看是否能找到yy'能与xx'匹配

最终可以得到最大匹配数,易看出这是贪心策略。时间复杂度为O(NM)O(NM)

luogu P3386 二分图匹配 模板题

 #include<bits/stdc++.h>
 using namespace std;
 const int MAXN = 1005;
 int vis[MAXN],lk[MAXN],head[MAXN];
 int n,m,cnt,f;
 struct edge{
     int u,v,w,next;
 }e[MAXN * MAXN];
 void insert(int u, int v){
     e[++cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt;
 }
 bool dfs(int u){
     for(int i = head[u]; i ; i = e[i].next){
         int v = e[i].v;
         if(!vis[v]){
             vis[v] = 1;
             if(!lk[v] || dfs(lk[v])){
                 lk[v] = u;
                 return 1;
             }
         }
     }
     return 0;
 }
 int main(){
     cin >> n >> m >> f;
     for(int i = 1; i <= f; i++){
         int u,v;
         scanf("%d %d", &u, &v);
         if(u > n || v > m || u < 1 || v < 1) continue;
         insert(u, v);
     }
     int ans = 0;
     for(int i = 1; i <= max(n, m); i++){
         memset(vis, 0, sizeof(vis));
         if(dfs(i)) ans++;
     }
     cout<<ans;
     return 0;
 }
 ```
 
**BZOJ 1059 矩阵游戏**

将行和列拆点,做二分图匹配判断是否为n

```c++
 #include<bits/stdc++.h>
 using namespace std;
 const int MAXN = 205;
 int mp[MAXN][MAXN];
 int vis[MAXN],lk[MAXN];
 int n;
 bool dfs(int u){
     for(int v = 1; v <= n; v++){
         if(mp[u][v] && !vis[v]){
             vis[v] = 1;
             if(!lk[v] || dfs(lk[v])){
                 lk[v] = u;
                 return 1;
             }
         }
     }
     return 0;
 }
 bool judge(){
     for(int i = 1; i <= n; i++){
         memset(vis, 0, sizeof(vis));
         if(!dfs(i)) return false;
     }
     return true;
 }
 int main(){
     int t;
     cin >> t;
     while(t--){
         cin >> n;
         memset(lk, 0, sizeof(lk));
         memset(mp, 0, sizeof(mp));
         for(int i = 1; i <= n; i++)
             for(int j = 1; j <= n; j++){
                 int x;
                 scanf("%d", &x);
                 mp[i][j] = x;
             }
         if(judge()) cout<<"Yes"<<endl;
         else cout<<"No"<<endl;
     }
     return 0;
 }
 ```