Python程式:查詢接受邀請的數量
假設有m個男孩和n個女孩,並且m = n。有一個派對即將到來,每個男孩都必須帶一個女孩參加派對。因此,男孩們邀請了所有的女孩,而一個女孩只能接受一個邀請。我們必須找出女孩可以接受的男孩邀請的總數。輸入以一個m x n矩陣的形式給出,其中每個單元格位置i,j表示男孩i是否已向女孩j傳送了邀請函。如果單元格為1,則表示已傳送邀請函,如果為0,則表示未傳送邀請函。
因此,如果輸入如下所示:
1 | 0 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
那麼輸出將為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
- 如果grid[node][nei]不為零且seen[nei]為False,則
- 返回False
- 對於nei從0到N,執行以下操作:
- 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
廣告