Chương trình tìm số lời mời được chấp nhận trong Python

Mô tả bài toán

Có m nam và n nữ (m = n). Mỗi nam mời tất cả nữ, mỗi nữ chỉ chấp nhận một lời mời. Cho ma trận m x n với grid[i][j] = 1 nếu nam i mời nữ j. Tìm số lượng lời mời tối đa được chấp nhận (ghép cặp tối đa).

Ví dụ

Ma trận:

1 0 0
1 0 1
1 1 0

Giải thuật (DFS + Hungarian Algorithm)

1. Hàm dfs(node, seen): tìm nữ nei chưa thăm mà nam node mời. Nếu nữ chưa được ghép hoặc nam hiện tại của nữ đó có thể tìm được người khác, ghép cặp.
2. Duyệt từng nam, reset mảng seen, gọi dfs. Đếm số lần ghép thành công.

Triển khai Python

def solve(grid):
    M, N = len(grid), len(grid[0])
    matching = [-1] * N
    def dfs(node, seen):
        for nei in range(N):
            if grid[node][nei] and not seen[nei]:
                seen[nei] = True
                if matching[nei] == -1 or dfs(matching[nei], seen):
                    matching[nei] = node
                    return True
        return False
    res = 0
    for i in range(M):
        seen = [False] * N
        if dfs(i, seen):
            res += 1
    return res

print(solve([[1, 0, 0], [1, 0, 1], [1, 1, 0]]))

Đầu vào

[[1, 0, 0], [1, 0, 1], [1, 1, 0]]

Đầu ra

3