Các cặp đôi nắm tay nhau trong C ++

Giả sử có N cặp đôi và họ đã ngồi trên 2 ghế xếp thành một hàng và muốn nắm tay nhau. Chúng ta phải tìm số lần hoán đổi tối thiểu để mọi cặp đôi ngồi cạnh nhau.

Người và ghế được biểu thị bằng một số từ 0 đến 2N-1, các cặp được đánh số theo thứ tự, điều này giống như cặp đầu tiên là (0, 1), cặp thứ hai là (2, 3), v.v. và cặp đôi cuối cùng là (2N-2, 2N-1).

Chỗ ngồi ban đầu của các cặp đôi được cung cấp bởi một mảng khác được gọi là hàng và hàng [i] là giá trị của người ban đầu ngồi ở ghế thứ i.

Vì vậy, nếu đầu vào là [0,2,4,1,3,5], thì đầu ra sẽ là 2

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một khối dữ liệu được gọi là UF, trong khối này xác định một số thuộc tính và chức năng như sau -
Xác định mảng cha mẹ
Khởi tạo khối UF bằng cách lấy giá trị N, sau đó thực hiện như sau -
đếm:=N
cha:=một mảng có kích thước N
để khởi tạo i:=0, khi i
- cha mẹ [i]:=i
cha mẹ [i]:=i
parA:=getParent (a)
parB:=getParent (b)
nếu parA giống như parB, thì -
- trở lại
(giảm số lượng đi 1)
cha [parB]:=parA
Xác định một hàm getParent (), điều này sẽ đưa tôi,
nếu cha mẹ [i] giống với tôi, thì -
- trả lại tôi
return parent [i] =getParent (parent [i])
Từ phương thức chính, thực hiện như sau -
n:=kích thước của hàng, N:=n / 2
tạo một khối UF được gọi là uf và khởi tạo với N
để khởi tạo gr:=0, khi gr
- a:=row [gr * 2]
- b:=row [gr * 2 + 1]
- gọi unionn (a / 2, b / 2) của uf
return N - số lượng uf

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Các cặp đôi nắm tay nhau trong C ++

Ví dụ

Đầu vào

Đầu ra