পাইথনে অদলবদল করার পরে সমতুল্য জোড়ার সংখ্যা সর্বাধিক করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে A সংখ্যার একটি তালিকা এবং একই দৈর্ঘ্যের B সংখ্যার তালিকা রয়েছে। আমাদের কাছে C সংখ্যার একটি 2D তালিকাও রয়েছে যেখানে প্রতিটি উপাদানের ফর্ম [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]], তাহলে আউটপুট 4 হবে, যেহেতু আমরা A[0] কে A[1] এর সাথে তারপর A[2] কে A[3] দিয়ে অদলবদল করতে পারি।

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

N :=A এর আকার
গ্রাফ :=প্রদত্ত প্রান্তগুলিকে দ্বিমুখীভাবে সংযুক্ত করে একটি গ্রাফ।
উত্তর :=0
দেখা হয়েছে :=N আকারের একটি তালিকা এবং False দিয়ে পূরণ করুন
আপনার জন্য 0 থেকে N রেঞ্জে, করুন
- যদি দেখা যায়[u] শূন্য হয়, তাহলে
  - সারি :=একটি সারি এবং সন্নিবেশ u
  - দেখেছি[u] :=সত্য
  - সারিতে থাকা প্রতিটি নোডের জন্য, করুন
    - গ্রাফ[নোড]-এ প্রতিটি nei-এর জন্য, করুন
      - যদি দেখা যায় [nei] মিথ্যা, তাহলে
        
        সারির শেষে nei ঢোকান
        
        দেখেছি [নিই] :=সত্য
  - গণনা :=একটি মানচিত্র যাতে সারিতে থাকা সকলের জন্য B[i] উপাদানের গণনা রয়েছে
  - সারিতে থাকা প্রতিটি i জন্য, করুন
    - যদি গণনা[A[i]] অ-শূন্য হয়, তাহলে
      - গণনা[A[i]] :=গণনা[A[i]] - 1
      - উত্তর :=উত্তর + ১
উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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]]