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

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

উদাহরণস্বরূপ, ইনপুট:

1	0	0
1	0	1
1	1	0

হলে আউটপুট হবে 3।

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

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

মেয়ে ২ ছেলে ৩-এর আমন্ত্রণ গ্রহণ করে।

মেয়ে ৩ ছেলে ২-এর আমন্ত্রণ গ্রহণ করে।

(এখানে ইন্ডেক্স ১ থেকে শুরু)

সমাধানের ধাপসমূহ (বিপার্টাইট ম্যাচিং / DFS)

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