পাইথনে সোয়াপ করে ইকুিভ্যালেন্ট পেয়ারের সর্বোচ্চ সংখ্যা বাড়ানোর প্রোগ্রাম

মান ল করুন A এবং B নামে সমান দৈর্ঘ্যের দুটি সংখ্যার তালিকা। আরো C নামের একটি ২D তালিকা যেখানে প্রতিটি এলিমেন্ট [i, j] ফর্মে, যা বোঝায় A[i] এবং A[j] যেকোনোবার সোয়াপ করা যায়। সোয়াপ করার পর A[i] = B[i] এমন পেয়ারের সর্বোচ্চ সংখ্যা খুঁজে বের করতে হবে।

যদি ইনপুট হয় A = [5, 6, 7, 8], B = [6, 5, 8, 7], C = [[0, 1],[2, 3]], তবে আউটপুট হবে ৪, কারণ A[0] ↔ A[1] এবং A[2] ↔ A[3] সোয়াপ করা যায়।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

N := A-এর আকার
graph := দিয়ে गये এজগুলো বাইডিরেকশনালি কানেক্ট করে একটি গ্রাফ
ans := 0
seen := N আকারের একটি তালিকা, False দিয়ে ভরা
u কে ০ থেকে N পর্যন্ত লুপ চালান:
- যদি seen[u] false হয়:
  - queue := একটি কিউ এবং u ডালুন, seen[u] := True
  - queue-এ থাকা প্রতিটি node-এর জন্য:
    - graph[node]-এ থাকা প্রতিটি nei-এর জন্য: যদি seen[nei] false, queue-এ nei যোগ করুন, seen[nei] := True
  - count := queue-এ থাকা সব i-এর জন্য B[i]-এর কাউন্ট ধারণকারী একটি ম্যাপ
  - queue-এ থাকা প্রতিটি i-এর জন্য: যদি count[A[i]] নন-জিরো, count[A[i]] কমানো, ans := ans + 1
ans ফেরত দিন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

উদাহরণ

from collections import Counter class Solution:    def solve(self, A, B, edges):       N = len(A)       graph = [[] for _ in range(N)]       for u, v in edges:          graph[u].append(v)          graph[v].append(u)       ans = 0       seen = [False] * N       for u in range(N):          if not seen[u]:             queue = [u]             seen[u] = True             for node in queue:                for nei in graph[node]:                   if not seen[nei]:                      queue.append(nei)                      seen[nei] = True             count = Counter(B[i] for i in queue)             for i in queue:                if count[A[i]]:                   count[A[i]] -= 1             ans += 1       return ans ob = Solution() A = [5, 6, 7, 8] B = [6, 5, 8, 7] C = [[0, 1],[2, 3]] print(ob.solve(A, B, C))

ইনপুট

[5, 6, 7, 8], [6, 5, 8, 7], [[0, 1],[2, 3]]