โปรแกรมค้นหาจำนวนคำเชิญที่ตอบรับใน Python

สมมติว่ามี m ชาย และ n หญิง และ m =n มีปาร์ตี้เข้ามาและเด็กผู้ชายแต่ละคนต้องไปกับผู้หญิงในงานปาร์ตี้นั้น ดังนั้นเด็กชายจึงเชิญเด็กหญิงทุกคนและเด็กหญิงสามารถตอบรับคำเชิญเดียวเท่านั้น เราต้องหาจำนวนคำเชิญทั้งหมดจากหนุ่มๆ ที่สาวๆ จะรับได้ ข้อมูลที่ป้อนจะได้รับในเมทริกซ์ขนาด m x n โดยที่แต่ละตำแหน่งของเซลล์ i, j แสดงว่าเด็กชาย i ได้ส่งจดหมายถึงเด็กหญิง j แล้ว หากเซลล์เป็น 1 แสดงว่าส่งคำเชิญแล้ว หากเป็น 0 แสดงว่าไม่มีการส่งคำเชิญ

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 3

ผลลัพธ์จะเป็น 3 ถ้า −

เด็กหญิง 1 ยอมรับคำเชิญของเด็กชาย 1

เด็กหญิง 2 ตอบรับคำเชิญของเด็กชาย 3

เด็กหญิง 3 ตอบรับคำเชิญของเด็กชาย 2

(ดัชนีเริ่มต้นที่ 1)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด เห็น
  • สำหรับ nei ในช่วง 0 ถึง N ให้ทำ
    • ถ้า grid[node][nei] ไม่ใช่ศูนย์และเห็น[nei] เป็นเท็จ ดังนั้น
      • เห็น[nei] :=จริง
      • หากmatch[nei] เหมือนกับ -1 หรือ dfs(matching[nei], seen) เป็นจริง ดังนั้น
        • จับคู่[nei] :=โหนด
        • คืนค่า True
  • คืนค่าเท็จ
• M:=จำนวนแถวของตาราง
• N :=จำนวนคอลัมน์ของกริด
• matching :=รายการขนาด N ที่มีค่า -1
• res :=0
• สำหรับฉันในช่วง 0 ถึง M ให้ทำ
  • เห็น :=รายการขนาด N ที่มีค่าเป็นเท็จ
  • ถ้า dfs(i, seen) เป็น True แล้ว
    • ผลตอบแทน
• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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