คู่นักรักจับมือกันใน C++

สมมติว่ามี N คู่นักรักนั่งบนที่นั่ง 2N ที่จัดเรียงเป็นแถว ต้องการจับมือกัน เราต้องหาจำนวนการสลับที่น้อยที่สุดเพื่อให้ทุกคู่นั่งติดกัน

คนและที่นั่งแทนด้วยตัวเลข 0 ถึง 2N-1 คู่เรียงลำดับ (0,1), (2,3), ..., (2N-2, 2N-1)

การจัดที่นั่งเริ่มต้นให้โดยอาร์เรย์ row โดย row[i] คือคนที่นั่งที่ i

เช่น [0,2,4,1,3,5] เอาต์พุตคือ 2

วิธีแก้ − ใช้ Union-Find จับกลุ่มคู่ที่นั่งผิดที่นั่ง คำนวนจำนวนการสลับจากจำนวนกลุ่ม

ตัวอย่าง

#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), parB = getParent(b); 
            if (parA == parB) return; 
            count--; parent[parB] = parA; 
        } 
        int getParent(int i){ return parent[i] == i ? i : parent[i] = getParent(parent[i]); } 
    }; 
    int minSwapsCouples(vector<int>& row) { 
        int n = row.size(), N = n / 2; 
        UF uf(N); 
        for (int gr = 0; gr < N; gr++) { 
            int a = row[gr * 2], b = row[gr * 2 + 1]; 
            uf.unionn(a / 2, b / 2); 
        } 
        return N - uf.count; 
    } 
}; 

main(){ 
    Solution ob; 
    vector<int> v = {0,2,4,1,3,5}; 
    cout << (ob.minSwapsCouples(v)); 
}

อินพุต

{0,2,4,1,3,5}