Road Map

二分图的定义

如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

充分必要条件

一个图是二分图，当且仅当图中不含有 奇数环；

反之，如果图中不含有奇数环，则一定是二分图

染色法判定二分图

1、一个图是二分图：当且仅当可以二染色

class Solution {
    int[] color;// 0:未染色；1：红色；2：黑色；（3-1=2，3-2=1）
    int n;
    int[][] graph;

    public boolean isBipartite(int[][] _graph) {
        graph = _graph;
        n = graph.length;
        color = new int[n];
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                if (!dfs(i, 1)) return false;
            }
        }
        return true;
    }

    boolean dfs(int i, int c) { // 是否可以对当前点进行二染色
        color[i] = c;
        for (int j : graph[i]) {
            if (color[j] == 0) {
                if (!dfs(j, 3 - c)) return false;
            } else {
                if (color[j] == c) return false;
            }
        }
        return true;
    }
}

匈牙利算法求二分图的最大匹配

题目：785. 判断二分图 (opens new window)

染色法判定二分图

染色法是判断二分图最常用的方法，当且仅当所有节点被染色，且没有冲突发生，证明该图是二分图

代码实现

• AcWing 860. 染色法判定二分图

#include <bits/stdc++.h>
using namespace std;

int n, m ;
const int N = 1e5+10;
int st[N]; // 0:未染色，1:红；-1;黑色(或者搞成0，1，2，用3-color换颜色)
unordered_map<int, vector<int>> edges;
bool paint(int x, int color){
    if (st[x]!=0) return st[x] == color;
    st[x] = color;
    for (auto &v: edges[x]){
        if (!paint(v, -color)) return false;
    }
    return true;
}
int main(){
    cin >> n >> m;
    int u, v;
    while (m--){
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    memset(st, 0 ,sizeof st);
    bool ans = true;
    for (int i = 1; i <=n; i++){
        if (!st[i]){
            if (!paint(i, 1)){ // 默认染成红色
                puts("No");
                ans = false;
                break;
            }
        }
    }
    if (ans)puts("Yes");
    return 0;
}

匈牙利算法

求二分图的最大匹配

模板

//match[j]=a,表示女孩j的现有配对男友是a
int match[N];
//st[]数组我称为临时预定数组，st[j]=a表示一轮模拟匹配中，女孩j被男孩a预定了。
int st[N];

//这个函数的作用是用来判断,如果加入x来参与模拟配对,会不会使匹配数增多
bool find(int x) {
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i]) {
        int j = e[i];
        if(!st[j]){//如果在这一轮模拟匹配中,这个女孩尚未被预定
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功,更新match
            if(!match[j]||find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}

//记录最大匹配
int res = 0;
for(int i = 1; i <= n1 ;i ++) {
    //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
    memset(st,false,sizeof st);
    if(find(i))
        res++;
}