C++-এ সব জোড়া মোজা একসাথে রাখতে ন্যূনতম সোয়াপ সংখ্যা বের করুন

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

যেমন ইনপুট row = [0, 5, 6, 2, 1, 3, 7, 4] হলে আউটপুট হবে ২, কারণ সারি অর্ডার হবে:

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

এটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

দুটি অ্যারে p এবং sz সংজ্ঞায়িত করুন
find() ফাংশন সংজ্ঞায়িত করুন, যা u নেবে এবং (p[u] == u হলে u রিটার্ন করবে, অন্যথায় find(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[pv]
অন্যথায় p[pu] := pv এবং sz[pv] += sz[pu]
মেইন মেথড থেকে n := arr.size()
p := সাইজ n এর অ্যারে, i=0 থেকে n-1 পর্যন্ত p[i] := i
sz := সাইজ n এর অ্যারে, সব ১ দিয়ে ফিল করুন
i=0 থেকে n-1 পর্যন্ত u := arr[i<<1]/2, v := arr[i<<1|1]/2, join(u,v)
ans := 0
i=0 থেকে n-1 পর্যন্ত যদি find(i)==i হয়, ans += sz[i]-1
ans রিটার্ন করুন

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে:

উদাহরণ

#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}