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

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

उदाहरण के लिए, यदि इनपुट है:

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

आउटपुट 3 होगा यदि:

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

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

हल करने के चरण

1. 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 वापस करें।
2. M := grid की पंक्ति संख्या
3. N := grid की कॉलम संख्या
4. matching := आकार N की सूची जिसमें मान -1 हो।
5. res := 0
6. i को 0 से M तक लूप चलाएं:
   • seen := आकार N की सूची जिसमें मान False हो।
   • यदि dfs(i, seen) True है, तो res += 1
7. 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