পাইথনে গৃহীত আমন্ত্রণের সংখ্যা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন m ছেলে এবং n মেয়ে, এবং m =n। একটি পার্টি ইনকামিং আছে, এবং প্রতিটি ছেলেকে একটি মেয়ের সাথে সেই পার্টিতে যেতে হবে। সুতরাং, ছেলেরা সব মেয়েদের আমন্ত্রণ জানায় এবং একটি মেয়ে শুধুমাত্র একটি আমন্ত্রণ গ্রহণ করতে পারে। আমাদের খুঁজে বের করতে হবে ছেলেদের কাছ থেকে মোট কতগুলো আমন্ত্রণ মেয়েরা গ্রহণ করতে পারবে। ইনপুটটি একটি m x n ম্যাট্রিক্সে দেওয়া হয়েছে, যেখানে প্রতিটি কোষের অবস্থান i, j বোঝায় যে ছেলেটি মেয়ে j কে একটি চিঠি পাঠিয়েছে কিনা। যদি একটি সেল 1 হয় তার মানে হল একটি আমন্ত্রণ পাঠানো হয়েছে, যদি এটি 0 হয় তাহলে কোন আমন্ত্রণ পাঠানো হয়নি৷

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 3.

আউটপুট হবে 3 যদি −

মেয়ে 1 ছেলে 1 এর আমন্ত্রণ গ্রহণ করে৷

মেয়ে 2 ছেলে 3 এর আমন্ত্রণ গ্রহণ করে।

মেয়ে 3 ছেলে 2 এর আমন্ত্রণ গ্রহণ করে।

(এখানে সূচক 1 থেকে শুরু হয়)

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড নেবে, দেখা
  • 0 থেকে N রেঞ্জের nei এর জন্য, করুন
    • যদি গ্রিড[নোড][nei] অ-শূন্য হয় এবং দেখা হয়[nei] মিথ্যা হয়, তাহলে
      • দেখেছি [নিই] :=সত্য
      • যদি ম্যাচিং[nei] -1 বা dfs(matching[nei], দেখা) এর মত হয়, তাহলে
        • ম্যাচিং[nei] :=নোড
        • সত্য ফেরান
  • মিথ্যে ফেরত দিন
• M:=গ্রিডের সারি গণনা
• N :=গ্রিডের কলাম সংখ্যা
• ম্যাচিং :=মান -1 ধারণকারী N আকারের একটি তালিকা
• res :=0
• আমি 0 থেকে M রেঞ্জের জন্য, কর
  • দেখা হয়েছে :=False মান ধারণকারী 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