用 Python 编写程序找出已接受邀请的数量

pythonserver side programmingprogramming更新于 2025/12/12 20:28:17

假设有 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
- 对于 0 到 N 范围内的 nei，执行
  - 如果 grid[node][nei] 非零且 seen[nei] 为 False，则
    - seen[nei] := True
    - 如果 matching[nei] 与 -1 相同或 dfs(matching[nei], seen) 为 True，则
      - matching[nei] := node
      - 返回 True
- 返回 False
M:= 网格的行数
N := 网格的列数
matching := 大小为 N 且值为 -1 的列表
res := 0
对于范围为 0 到 M 的 i，执行
- 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]]))