โปรแกรมหาจำนวนคำเชิญที่ถูกตอบรับใน Python

สมมติว่ามี m หนุ่ม n สาว (m=n) มีงานปาร์ตี้ แต่ละหนุ่มต้องไปกับสาวคนละคน หนุ่มเชิญสาวทั้งหมด สาวรับเชิญได้คนละ 1 ราย ให้หาจำนวนคำเชิญที่ถูกตอบรับสูงสุด ให้มาในรูปเมทริกซ์ m×n ที่ grid[i][j]=1 หมายถึงหนุ่ม i เชิญสาว j

ตัวอย่าง: เมทริกซ์ 3×3 ผลลัพธ์ 3

วิธีแก้ปัญหา (Maximum Bipartite Matching - DFS)

1. ฟังก์ชัน dfs(node, seen):
   • วน nei ทุกคอลัมน์:
     • ถ้า grid[node][nei] และยังไม่ seen[nei]:
       • seen[nei] = True
       • ถ้า matching[nei] == -1 หรือ dfs(matching[nei], seen): matching[nei] = node, คืน True
   • คืน False
2. M, N := ขนาด grid, matching := [-1]*N, res := 0
3. วน i ทุกแถว: seen := [False]*N, ถ้า dfs(i, seen): res += 1
4. คืน res

ตัวอย่างโค้ด

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]]))

อินพุต

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

เอาต์พุต

3