पायथन में स्वीकृत आमंत्रणों की संख्या का पता लगाने का कार्यक्रम

मान लीजिए कि वहाँ m लड़के और n लड़कियाँ हैं, और m =n हैं। एक पार्टी आ रही है, और प्रत्येक लड़के को उस पार्टी में एक लड़की के साथ जाना है। तो, लड़के सभी लड़कियों को आमंत्रित करते हैं और एक लड़की केवल एक आमंत्रण स्वीकार कर सकती है। हमें लड़कों से कुल कितने आमंत्रणों का पता लगाना है जिन्हें लड़कियां स्वीकार कर सकती हैं। इनपुट एमएक्सएन मैट्रिक्स में दिया गया है, जहां प्रत्येक सेल स्थिति i, j यह दर्शाता है कि लड़के ने लड़की को एक पत्र भेजा है या नहीं। अगर सेल 1 है तो इसका मतलब है कि आमंत्रण भेजा गया है, अगर यह 0 है तो इसका मतलब है कि कोई आमंत्रण नहीं भेजा गया है।

तो, अगर इनपुट पसंद है

तो आउटपुट 3 होगा।

आउटपुट 3 होगा अगर -

लड़की 1 लड़के 1 का निमंत्रण स्वीकार करती है।

लड़की 2 ने लड़के 3 का निमंत्रण स्वीकार किया।

लड़की 3 लड़के 2 के निमंत्रण को स्वीकार करती है।

(यहां इंडेक्स 1 से शुरू होता है)

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा, देखा
  • एनई के लिए 0 से एन तक, करें
    • अगर ग्रिड [नोड] [नेई] शून्य नहीं है और देखा गया है [नेई] गलत है, तो
      • देखा[nei] :=सच
      • यदि मिलान [nei] -1 या dfs के समान है (मिलान [nei], देखा गया) सत्य है, तो
        • मिलान करना[nei] :=नोड
        • सही लौटें
  • झूठी वापसी
• M:=ग्रिड की पंक्ति गणना
• N :=ग्रिड की कॉलम संख्या
• मिलान:=आकार N की एक सूची जिसमें मान -1 है
• res :=0
• 0 से M की श्रेणी में i के लिए, करें
  • देखा:=आकार N की एक सूची जिसमें मान गलत है
  • यदि dfs(i, देखा गया) सत्य है, तो
    • रिटर्न रेस
• रिटर्न रेस

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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