দম্পতিরা C++ এ হাত ধরে আছে

ধরুন সেখানে N দম্পতি আছে এবং তারা সারিবদ্ধভাবে সাজানো 2N আসনে বসে আছে এবং হাত ধরতে চায়। আমাদের ন্যূনতম সংখ্যক অদলবদল খুঁজে বের করতে হবে যাতে প্রতিটি দম্পতি পাশাপাশি বসে থাকে।

মানুষ এবং আসনগুলি 0 থেকে 2N-1 পর্যন্ত একটি সংখ্যা দ্বারা প্রতিনিধিত্ব করা হয়, দম্পতিগুলিকে ক্রমানুসারে সংখ্যা করা হয়, এটি প্রথম দম্পতির মতো (0, 1), দ্বিতীয় দম্পতি (2, 3) এবং আরও অনেক কিছু। শেষ দম্পতি (2N-2, 2N-1) হিসাবে।

দম্পতিদের প্রাথমিক আসনটি সারি নামে আরেকটি অ্যারে দ্বারা দেওয়া হয় এবং সারি [i] যে ব্যক্তি প্রাথমিকভাবে i-ম আসনে বসে থাকে তার মান।

সুতরাং, ইনপুট যদি [0,2,4,1,3,5] এর মত হয়, তাহলে আউটপুট হবে 2

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

• UF নামক ডেটার একটি ব্লক সংজ্ঞায়িত করুন, এই ব্লকে নিম্নরূপ কিছু বৈশিষ্ট্য এবং ফাংশন সংজ্ঞায়িত করুন -

• একটি অ্যারে অভিভাবক সংজ্ঞায়িত করুন

• N একটি মান নিয়ে UF ব্লক শুরু করুন, তারপর নিম্নলিখিতগুলি করুন −

• গণনা :=N

• অভিভাবক :=আকারের একটি বিন্যাস N

• আরম্ভ করার জন্য i :=0, যখন i

  • পিতামাতা[i] :=i

• পিতামাতা[i] :=i

• parA :=getParent(a)

• parB :=getParent(b)

• যদি parA parB এর মত হয়, তাহলে −

  • ফেরত

• (গণনা 1 দ্বারা হ্রাস করুন)

• পিতামাতা[parB] :=parA

• একটি ফাংশন সংজ্ঞায়িত করুন getParent(), এটি i,

  লাগবে

• যদি অভিভাবক[i] i এর মতো হয়, তাহলে −

  • ফেরত i

• রিটার্ন প্যারেন্ট[i] =getParent(অভিভাবক[i])

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• n :=সারির আকার, N :=n / 2

• uf নামে একটি UF ব্লক তৈরি করুন এবং N

  দিয়ে আরম্ভ করুন

• শুরু করার জন্য gr :=0, যখন gr

  • a :=সারি [gr * 2]

  • b :=সারি [gr * 2 + 1]

  • uf

    এর unionn(a / 2, b / 2) কল করুন

• ফেরত N - uf এর গণনা

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   class UF{
      public:
      vector<int> parent;
      int count;
      UF(int N){
         count = N;
         parent = vector<int>(N);
         for (int i = 0; i < N; i++) {
            parent[i] = i;
         }
      }
      void unionn(int a, int b){
         int parA = getParent(a);
         int parB = getParent(b);
         if (parA == parB)
         return;
         count--;
         parent[parB] = parA;
      }
      int getParent(int i){
         if (parent[i] == i)
         return i;
         return parent[i] = getParent(parent[i]);
      }
   };
   int minSwapsCouples(vector<int>& row) {
      int n = row.size();
      int N = n / 2;
      UF uf(N);
      for (int gr = 0; gr < N; gr++) {
         int a = row[gr * 2];
         int b = row[gr * 2 + 1];
         uf.unionn(a / 2, b / 2);
      }
      return N - uf.count;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,2,4,1,3,5};
   cout << (ob.minSwapsCouples(v));
}

ইনপুট

{0,2,4,1,3,5}

আউটপুট

2