C++ में हाथ पकड़े हुए युगल

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

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

जोड़ों की प्रारंभिक बैठक पंक्ति नामक एक अन्य सरणी द्वारा दी जाती है, और पंक्ति [i] उस व्यक्ति का मान होता है जो प्रारंभ में i-वें स्थान पर बैठा होता है।

तो, अगर इनपुट [0,2,4,1,3,5] जैसा है, तो आउटपुट 2

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• यूएफ नामक डेटा के एक ब्लॉक को परिभाषित करें, इस ब्लॉक में कुछ गुणों और कार्यों को निम्नानुसार परिभाषित करें -

• सरणी पैरेंट को परिभाषित करें

• N मान लेकर UF ब्लॉक को इनिशियलाइज़ करें, फिर निम्न कार्य करें -

• गिनती :=एन

• पैरेंट:=आकार की एक सरणी N

• इनिशियलाइज़ i :=0 के लिए, जब i

  • माता-पिता [i] :=i

• माता-पिता [i] :=i

• पैरा:=माता-पिता (ए) प्राप्त करें

• parB :=getParent(b)

• यदि पैरा, पैराबी के समान है, तो -

  • वापसी

• (गिनती 1 से घटाएं)

• माता-पिता [parB] :=paraA

• getParent() फ़ंक्शन को परिभाषित करें, इसमें मुझे लगेगा,

• अगर पैरेंट [i] i के समान है, तो -

  • वापसी मैं

• वापसी माता-पिता [i] =getParent (माता-पिता [i])

• मुख्य विधि से निम्न कार्य करें -

• n:=पंक्ति का आकार, N:=n/2

• यूएफ नामक एक यूएफ ब्लॉक बनाएं और एन के साथ आरंभ करें

• जीआर शुरू करने के लिए:=0, जब जीआर <एन, अपडेट करें (1 से जीआर बढ़ाएं), करें -

  • ए:=पंक्ति [जीआर * 2]

  • बी:=पंक्ति [जीआर * 2 + 1]

  • यूएफ के यूनियन (ए / 2, बी / 2) को कॉल करें

• वापसी एन - यूएफ की गिनती

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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