Pythonで受け入れられた招待状の数を調べるプログラム

m人の男の子とn人の女の子がいて、m=nであるとします。入ってくるパーティーがあり、それぞれの男の子は女の子と一緒にそのパーティーに行かなければなりません。したがって、男の子はすべての女の子を招待し、女の子は1つの招待のみを受け入れることができます。女の子が受け入れることができる男の子からの招待の総数を知る必要があります。入力はmxn行列で与えられます。ここで、各セル位置i、jは、男の子iが女の子jに手紙を送ったかどうかを示します。セルが1の場合は招待状が送信されたことを意味し、0の場合は招待状が送信されていないことを意味します。

したがって、入力が次のような場合

その場合、出力は3になります。

−

女の子1は男の子1の招待を受け入れます。

女の子2は男の子3の招待を受け入れます。

女の子3は男の子2の招待を受け入れます。

（ここではインデックスは1から始まります）

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これはノードを取ります、見られます
  • 0からNの範囲のneiについては、
    • grid [node] [nei]がゼロ以外で、seen [nei]がFalseの場合、
      • sawed [nei]：=True
      • matching [nei]が-1と同じであるか、dfs（matching [nei]、seen）がTrueの場合、
        • matching [nei]：=node
        • Trueを返す
  • Falseを返す
• M：=グリッドの行数
• N：=グリッドの列数
• matching：=値-1を含むサイズNのリスト
• res：=0
• 0からMの範囲のiについては、
  • sawed：=値Falseを含むサイズNのリスト
  • dfs（i、seen）がTrueの場合、
    • return res
• return 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