在 Python 中找出已接受邀请数量的程序
假设有m个男孩和n个女孩,并且m=n。有一个派对即将到来,每个男孩都必须和一个女孩一起去参加那个派对。所以,男孩邀请所有女孩,一个女孩只能接受一个邀请。我们必须找出女孩可以接受的男孩邀请总数。输入在amxn矩阵中给出,其中每个单元格位置i,j表示男孩i是否给女孩j发送了一封信。如果单元格为1,则表示已发送邀请,如果为0,则表示未发送邀请。
所以,如果输入是这样的
那么输出将是3。
如果-输出将为3
女孩1接受男孩1的邀请。
女孩2接受男孩3的邀请。
女孩3接受男孩2的邀请。
(这里索引从1开始)
示例
让我们看看以下实现以获得更好的理解-
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
热门推荐
1 训练狗狗搜寻
2 如何训练狗狗装死
3 狗狗训练书
6 怎么训练狗狗拜年
8 狗狗训练游戏
10 狗狗嗅觉训练
11 怎么训练狗狗在笼子里不叫
12 怎么训练狗狗站立走路
13 怎么训练狗狗在马桶上
14 狗狗尿尿怎么训练
15 训练狗狗用品
16 泰迪狗狗的训练方法大小便
17 训练狗狗可以打吗
18 王曼丽的狗狗训练