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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告