परिचय
मान लीजिए हमारे पास row नामक संख्याओं की एक सूची है और यह एक पंक्ति में पड़े मोज़े (socks) को दर्शाती है। वे सॉर्टेड नहीं हैं, लेकिन हम उन्हें पुनर्व्यवस्थित करना चाहते हैं ताकि मोज़े की प्रत्येक जोड़ी अगल-बगल हो जैसे (0, 1), (2, 3), (4, 5), और इसी तरह। हमें उन्हें पुनर्व्यवस्थित करने के लिए आवश्यक न्यूनतम स्वैप्स (swaps) की संख्या ढूंढनी है।
तो, यदि इनपुट row = [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]
समाधान दृष्टिकोण
यूनियन-फाइंड (डिसजॉइंट सेट यूनियन - DSU) का उपयोग करके। प्रत्येक जोड़ी (0,1), (2,3), ... को एक घटक मानें। वर्तमान व्यवस्था में, यदि एक स्लॉट में जोड़ी u का मोजा और अगले स्लॉट में जोड़ी v का मोजा है, तो u और v को यूनियन करें। उत्तर Σ(size(component) - 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);
return 0;
}
इनपुट
{0, 5, 6, 2, 1, 3, 7, 4}
आउटपुट
2
नोट
मूल आउटपुट में "23" था जो गलत प्रतीत होता है। सही आउटपुट 2 है जैसा कि चरण-दर-चरण उदाहरण में दिखाया गया है।
निष्कर्ष
DSU-आधारित समाधान O(n α(n)) समय में न्यूनतम स्वैप्स की गणना करता है। प्रत्येक कनेक्टेड कंपोनेंट के आकार k के लिए k-1 स्वैप्स की आवश्यकता होती है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।