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

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

ผู้คนและที่นั่งแสดงด้วยตัวเลขตั้งแต่ 0 ถึง 2N-1 คู่รักจะเรียงลำดับกัน เช่น คู่แรกเป็น (0, 1) คู่ที่สองเป็น (2, 3) เป็นต้น คู่สุดท้ายเป็น (2N-2, 2N-1)

ที่นั่งเริ่มต้นของคู่รักจะได้รับจากอาร์เรย์อื่นที่เรียกว่า row และ row[i] เป็นค่าของผู้ที่นั่งในที่นั่ง i-th ในขั้นต้น

ดังนั้นหากอินพุตเป็น [0,2,4,1,3,5] เอาต์พุตจะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งบล็อกของข้อมูลที่เรียกว่า UF ในบล็อกนี้ให้กำหนดคุณสมบัติและฟังก์ชันบางอย่างดังนี้ -

• กำหนดพาเรนต์อาร์เรย์

• เริ่มต้นบล็อก UF โดยใช้ค่า N จากนั้นทำดังต่อไปนี้ −

• นับ :=N

• parent :=อาร์เรย์ขนาด N

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • parent[i] :=i

• parent[i] :=i

• พาร์ :=getParent(ก)

• parB :=getParent(b)

• ถ้า parA เหมือนกับ parB แล้ว −

  • กลับ

• (ลดจำนวนลง 1)

• ผู้ปกครอง[parB] :=parA

• กำหนดฟังก์ชัน getParent() ซึ่งต้องใช้ i

• ถ้า parent[i] เหมือนกับ i แล้ว −

  • กลับมา

• ส่งคืนพาเรนต์[i] =getParent(พาเรนต์[i])

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• n :=ขนาดแถว, N :=n / 2

• สร้างบล็อก UF หนึ่งบล็อกที่เรียกว่า uf และเริ่มต้นด้วย N

• สำหรับการเริ่มต้น gr :=0 เมื่อ gr

  • a :=row[gr * 2]

  • b :=row[gr * 2 + 1]

  • โทร unionn(a / 2, b / 2) ของ uf

• return N - นับ uf

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,2,4,1,3,5};
   cout << (ob.minSwapsCouples(v));
}

อินพุต

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

ผลลัพธ์

2