Python程式:查詢接受邀請的數量


假設有m個男孩和n個女孩,並且m = n。有一個派對即將到來,每個男孩都必須帶一個女孩參加派對。因此,男孩們邀請了所有的女孩,而一個女孩只能接受一個邀請。我們必須找出女孩可以接受的男孩邀請的總數。輸入以一個m x n矩陣的形式給出,其中每個單元格位置i,j表示男孩i是否已向女孩j傳送了邀請函。如果單元格為1,則表示已傳送邀請函,如果為0,則表示未傳送邀請函。

因此,如果輸入如下所示:

100
101
110

那麼輸出將為3。

如果 - 輸出將為3

女孩1接受男孩1的邀請。

女孩2接受男孩3的邀請。

女孩3接受男孩2的邀請。

(此處索引從1開始)

為了解決這個問題,我們將遵循以下步驟 -

  • 定義一個函式dfs()。它將接收節點和seen作為引數。
    • 對於nei從0到N,執行以下操作:
      • 如果grid[node][nei]不為零且seen[nei]為False,則
        • seen[nei] := True
        • 如果matching[nei]等於-1或dfs(matching[nei], seen)為True,則
          • matching[nei] := node
          • 返回True
    • 返回False
  • M := grid的行數
  • N := grid的列數
  • matching := 一個大小為N的列表,其值均為-1
  • res := 0
  • 對於i從0到M,執行以下操作:
    • seen := 一個大小為N的列表,其值均為False
    • 如果dfs(i, seen)為True,則
      • 返回res
  • 返回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

更新於: 2021年10月7日

217 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告