用Python计算接受邀请的数量程序

假设有m个男孩和n个女孩，且m = n。有一个聚会临近，每个男孩都必须与一个女孩一起参加。因此，男孩们邀请所有女孩，女孩只能接受一份邀请。我们必须找出女孩可以接受男孩发出的邀请的总数。输入以m x n的矩阵给出，其中每个单元格位置i，j表示男孩i是否向女孩j发送了一封信。如果单元格为1，则表示已发出邀请，如果为0，则表示未发送邀请。

因此，如果输入如下:

1	0	0
1	0	1
1	1	0

那么输出将为3。

如果-

女孩1接受男孩1的邀请

女孩2接受男孩3的邀请

女孩3接受男孩2的邀请

（这里索引从1开始）

为了解决这个问题，我们将遵循以下步骤 –

定义函数dfs（）。这将接受节点，seen
- 对于从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的列数
匹配：包含值-1的大小为N的列表
res：= 0
对于i从0到M做
- seen：包含值False的大小为N的列表
- 如果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或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

    返回res

打印（solve（[[1，0，0]，[1，0，1]，[1，1，0]]））