C++ में जोड़े हाथ पकड़ना (Couples Holding Hands) - न्यूनतम स्वैप

समस्या विवरण

N जोड़े (couples) हैं जो 2N सीटों पर एक पंक्ति में बैठे हैं और हाथ पकड़ना चाहते हैं। हमें न्यूनतम स्वैप (swaps) की संख्या ज्ञात करनी है ताकि हर जोड़ा अगल-बगल बैठ जाए।

लोग और सीटें 0 से 2N-1 तक संख्यांकित हैं। जोड़े क्रम में हैं: पहला जोड़ा (0, 1), दूसरा (2, 3), ..., अंतिम (2N-2, 2N-1)।

प्रारंभिक बैठने की व्यवस्था सरणी row द्वारा दी गई है जहां row[i] i-वीं सीट पर बैठे व्यक्ति का मान है।

उदाहरण

इनपुट

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

आउटपुट

2

समाधान दृष्टिकोण (यूनियन-फाइंड / डिस्जॉइंट सेट यूनियन)

प्रत्येक जोड़े को एक नोड मानें। वर्तमान बैठने में, प्रत्येक आसन्न सीट जोड़ी (row[2k], row[2k+1]) दो जोड़ों को जोड़ती है। उन्हें यूनियन-फाइंड में मर्ज करें। अंत में, आवश्यक स्वैप = N - जुड़े घटकों की संख्या।

कार्यकारी प्रोग्राम

#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 unite(int a, int b) {
            int parA = find(a);
            int parB = find(b);
            if (parA == parB) return;
            count--;
            parent[parB] = parA;
        }
        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(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.unite(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);
    return 0;
}

आउटपुट

2