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

Giả sử có m trai và n gái, và m =n. Có một bữa tiệc sắp đến, và mỗi chàng trai phải đi với một cô gái đến bữa tiệc đó. Vì vậy, các chàng trai mời tất cả các cô gái và một cô gái chỉ được nhận một lời mời. Chúng ta phải tìm ra tổng số lời mời từ các chàng trai mà các cô gái có thể chấp nhận. Dữ liệu đầu vào được đưa ra dưới dạng ma trận m x n, trong đó mỗi ô vị trí i, j biểu thị liệu chàng trai tôi có gửi thư cho cô gái j hay không. Nếu một ô là 1, nghĩa là một lời mời đã được gửi, nếu nó là 0, nghĩa là không có lời mời nào được gửi.

Vì vậy, nếu đầu vào giống như

1	0	0
1	0	1
1	1	0

thì đầu ra sẽ là 3.

Đầu ra sẽ là 3 nếu -

Cô gái 1 chấp nhận lời mời của chàng trai 1.

Cô gái 2 chấp nhận lời mời của cậu 3.

Cô gái 3 chấp nhận lời mời của chàng trai 2.

(ở đây chỉ mục bắt đầu từ 1)

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một hàm dfs (). Điều này sẽ lấy nút, được nhìn thấy
- đối với nei trong phạm vi từ 0 đến N, thực hiện
  - nếu lưới [node] [nei] khác 0 và nhìn thấy [nei] là Sai, thì
    - saw [nei]:=True
    - nếu đối sánh [nei] giống -1 hoặc dfs (đối sánh [nei], đã thấy) là Đúng, thì
      - khớp [nei]:=nút
      - trả về True
- trả về Sai
M:=số hàng của lưới
N:=số cột của lưới
phù hợp:=danh sách kích thước N chứa giá trị -1
res:=0
đối với tôi trong phạm vi từ 0 đến M, thực hiện
- saw:=danh sách kích thước N chứa giá trị Sai
- nếu dfs (i, saw) là True, thì
  - trả lại res
trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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