C++ এ একসাথে সব জোড়া মোজা সাজানোর জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অদলবদল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সারি নামে একটি সংখ্যার তালিকা রয়েছে এবং এটি একটি সারিতে থাকা মোজাগুলিকে প্রতিনিধিত্ব করছে। এগুলি সাজানো হয় না, তবে আমরা সেগুলিকে পুনরায় সাজাতে চাই যাতে প্রতিটি জোড়া মোজা পাশাপাশি থাকে যেমন (0, 1), (2, 3), (4, 5) এবং আরও অনেক কিছু। আমাদের তাদের পুনর্বিন্যাস করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অদলবদল খুঁজে বের করতে হবে।

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

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

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

একটি অ্যারে পি এবং অন্য অ্যারে sz
সংজ্ঞায়িত করুন
একটি ফাংশন সংজ্ঞায়িত করুন find(), এটি আপনাকে নিয়ে যাবে,
প্রত্যাবর্তন (যদি p[u] u এর মতো হয়, তাহলে u, অন্যথায় খুঁজুন(p[u]) এবং p[u] :=find(p[u]))
একটি ফাংশন join() সংজ্ঞায়িত করুন, এটি u, v,
লাগবে
pu :=find((u), pv :=find(v))
যদি pu pv এর মত হয়, তাহলে −
- ফেরত
যদি sz[pu]>=sz[pv] হয়, তাহলে −
- p[pv] :=pu
- sz[pu] :=sz[pu] + sz[pv]
অন্যথায়
- p[pu] :=pv
- sz[pv] :=sz[pv] + sz[pu]
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
n :=arr এর আকার
p :=আকারের একটি অ্যারে n
আরম্ভ করার জন্য i :=0, যখন i
- p[i] :=i
sz :=n আকারের একটি অ্যারে এবং 1 দিয়ে পূরণ করুন
আরম্ভ করার জন্য i :=0, যখন i
- u :=arr[i/2] / 2
- v :=arr[(i/2) বা 1] / 2
- যোগ দিন(u, v)
উত্তর :=0
আরম্ভ করার জন্য i :=0, যখন i
- যদি find(i) i এর মত হয়, তাহলে −
  - ans :=ans + sz[i] − 1
- উত্তর ফেরত দিন

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int find(int u) {
   return p[u] == u ? u : p[u] = find(p[u]);
}
void join(int u, int v) {
   int pu = find(u), pv = find(v);
   if (pu == pv)
   return;
   if (sz[pu] >= sz[pv]) {
      p[pv] = pu;
      sz[pu] += sz[pv];
   }else {
      p[pu] = pv;
      sz[pv] += sz[pu];
   }
}
int solve(vector<int>& arr) {
   int n = arr.size() / 2;
   p = vector<int>(n);
   for (int i = 0; i < n; ++i)
   p[i] = i;
   sz = vector<int>(n, 1);
   for (int i = 0; i < n; ++i) {
      int u = arr[i << 1] / 2;
      int v = arr[i << 1 | 1] / 2;
      join(u, v);
   }
   int ans = 0;
   for (int i = 0; i < n; ++i)
   if (find(i) == i)
   ans += sz[i] − 1;
   return ans;
}
int main(){
   vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
   cout << solve(v);
}

ইনপুট

{2, 4, 6, 3}