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

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

UF라는 데이터 블록 하나를 정의합니다. 이 블록에서 다음과 같이 일부 속성과 기능을 정의합니다. -
배열 부모 정의
값 N을 취하여 UF 블록을 초기화하고 다음을 수행하십시오 -
개수 :=N
parent :=N 크기의 배열
initialize i :=0의 경우, i
- 부모[i] :=나는
부모[i] :=나는
paraA :=getParent(a)
parB :=getParent(b)
parA가 parB와 같으면 -
- 반환
(1씩 감소)
부모[parB] :=parA
getParent() 함수를 정의하면 i가 필요합니다.
부모[i]가 i와 같으면 -
- 반환 i
부모[i] 반환 =getParent(부모[i])
주요 방법에서 다음을 수행하십시오 -
n :=행의 크기, N :=n / 2
uf라는 하나의 UF 블록을 만들고 N
으로 초기화합니다.
초기화 gr :=0의 경우 gr
- a :=행[gr * 2]
- b :=행[gr * 2 + 1]
- uf
  의 unionn(a / 2, b / 2) 호출
반환 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}