ধরুন N জোড়া দাম্পতি ২N সংখ্যক সিটে বসে আছে এবং সবাই হাত ধরে বসতে চায়। আমাদের কাজ হল কমপক্ষে কতবার সোয়াপ করলে সব জোড়া পাশাপাশি বসে যাবে তা বের করা।
মানুষ এবং সিটগুলো ০ থেকে ২N-1 পর্যন্ত সংখ্যায় উপস্থাপিত। জোড়াগুলো ক్రమাগত: প্রথম জোড়া (০, ১), দ্বিতীয় জোড়া (২, ৩), ..., শেষ জোড়া (২N-২, ২N-১)।
উদাহরণ
ইনপুট: [0,2,4,1,3,5] → আউটপুট: 2
সমাধানের ধাপসমূহ
- Union-Find (Disjoint Set Union) ডেটা স্ট্রাকচার ব্যবহার করুন।
- প্রতিটি সিট পেয়ারের জন্য (সিট ০-১, ২-৩, ...) যেসব জোড়া বসে আছে তাদের ইউনিয়ন করুন।
- উত্তর = মোট জোড়া সংখ্যা - কnected কম্পোনেন্টের সংখ্যা।
প্রোগ্রাম উদাহরণ
#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;
}
};
int main() {
Solution ob;
vector<int> v = {0,2,4,1,3,5};
cout << (ob.minSwapsCouples(v));
}
ইনপুট
{0,2,4,1,3,5}
আউটপুট
2
