二分图匹配模板

一句话说明

Hopcroft-Karp 不是一次找一条增广路，而是先用 BFS 分层，再用 DFS 一次找出多条最短增广路。

模板适用场景

• 左右两侧配对
• 一个左点最多匹配一个右点
• 求最大匹配数

如果题目只是判定是不是二分图，不必上这个模板。

Go 模板：Hopcroft-Karp

左侧点编号 0..leftSize-1，右侧点编号 0..rightSize-1。

func HopcroftKarp(adjacency [][]int, rightSize int) (int, []int, []int) {
    leftSize := len(adjacency)
    matchLeft := make([]int, leftSize)
    matchRight := make([]int, rightSize)
    dist := make([]int, leftSize)
 
    for i := range matchLeft {
        matchLeft[i] = -1
    }
    for i := range matchRight {
        matchRight[i] = -1
    }
 
    bfs := func() bool {
        queue := []int{}
        found := false
 
        for left := 0; left < leftSize; left++ {
            if matchLeft[left] == -1 {
                dist[left] = 0
                queue = append(queue, left)
            } else {
                dist[left] = -1
            }
        }
 
        for len(queue) > 0 {
            left := queue[0]
            queue = queue[1:]
 
            for _, right := range adjacency[left] {
                pairedLeft := matchRight[right]
                if pairedLeft == -1 {
                    found = true
                } else if dist[pairedLeft] == -1 {
                    dist[pairedLeft] = dist[left] + 1
                    queue = append(queue, pairedLeft)
                }
            }
        }
 
        return found
    }
 
    var dfs func(left int) bool
    dfs = func(left int) bool {
        for _, right := range adjacency[left] {
            pairedLeft := matchRight[right]
            if pairedLeft == -1 || (dist[pairedLeft] == dist[left]+1 && dfs(pairedLeft)) {
                matchLeft[left] = right
                matchRight[right] = left
                return true
            }
        }
        dist[left] = -1
        return false
    }
 
    matching := 0
    for bfs() {
        for left := 0; left < leftSize; left++ {
            if matchLeft[left] == -1 && dfs(left) {
                matching++
            }
        }
    }
 
    return matching, matchLeft, matchRight
}

这个模板的关键不变量

• matchLeft[u] 表示左点 u 当前匹配到哪个右点
• matchRight[v] 表示右点 v 当前匹配到哪个左点
• DFS 只能沿 BFS 建出的最短增广路层次继续走

为什么比朴素增广路快

朴素做法通常一次只增广一条路。
Hopcroft-Karp 会在同一轮层次图里尽量批量增广多条最短路，所以整体复杂度更优。

易错点

二分图匹配模板最容易错的地方

• 邻接表默认只从左侧指向右侧。
• 左右编号空间是分开的，不要混成一个数组下标体系。
• DFS 不能脱离 BFS 层次随便走。

复杂度

指标	复杂度
时间复杂度	O(E * sqrt(V))
空间复杂度	O(V + E)

相关主题

• 网络流与最大流
• 图算法

---

返回：算法模板