二分图

概念讲解

什么是二分图？

顶点可以分成两个集合，所有边的两端分别在两个集合中。

性质

• 没有奇数长度的环
• 可以用两种颜色染色

二分图判定（染色法）

123456789101112131415161718int color[N];

bool dfs(int u, int c) {
    color[u] = c;
    for (int v : graph[u]) {
        if (color[v] == c) return false;
        if (color[v] == 0 && !dfs(v, 3 - c)) return false;
    }
    return true;
}

bool isBipartite(int n) {
    memset(color, 0, sizeof(color));
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && !dfs(i, 1)) return false;
    }
    return true;
}

匈牙利算法（最大匹配）

1234567891011121314151617181920212223int match[N];
bool visited[N];

bool dfs(int u) {
    for (int v : graph[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        if (match[v] == 0 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian(int n) {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, false, sizeof(visited));
        if (dfs(i)) ans++;
    }
    return ans;
}

Konig 定理

最大匹配数 = 最小点覆盖数

考点分析

初赛考查方式

1. 程序阅读： 二分图算法
2. 编程题： 匹配问题

常见考点

• 二分图判定
• 最大匹配
• 最小点覆盖

练习题

1. 二分图的充要条件是什么？

2. 匈牙利算法的时间复杂度是多少？

3. Konig 定理的内容是什么？

易错点

⚠️ 注意：

1. 染色法可以判定二分图
2. 匈牙利算法是 O(nm)
3. 最大匹配 = 最小点覆盖
4. 二分图没有奇环