Python中如何实现Hopcroft-Karp算法？

from collections import deque

def hopcroft_karp(graph):
    def bfs():
        queue = deque()
        for u in U:
            if not match_U[u]:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = float('inf')
        dist[None] = float('inf')
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if dist[match_V[v]] == float('inf'):
                    dist[match_V[v]] = dist[u] + 1
                    queue.append(match_V[v])
        return dist[None] != float('inf')

    def dfs(u):
        if u is None:
            return True
        for v in graph[u]:
            if dist[match_V[v]] == dist[u] + 1:
                if dfs(match_V[v]):
                    match_V[v] = u
                    match_U[u] = v
                    return True
        dist[u] = float('inf')
        return False

    U = set(graph.keys())
    V = set(v for u in graph for v in graph[u])
    match_U = {u: None for u in U}
    match_V = {v: None for v in V}
    dist = {}

    matching = 0
    while bfs():
        for u in U:
            if not match_U[u]:
                if dfs(u):
                    matching += 1

    return matching, match_U

# 示例图
graph = {
    1: [4, 5],
    2: [4, 5, 6],
    3: [5, 6]
}

max_matching, matching = hopcroft_karp(graph)
print(f"最大匹配数: {max_matching}")
print("匹配结果:", matching)