सी ++ में सभी जोड़ी मोजे को एक साथ व्यवस्थित करने के लिए आवश्यक न्यूनतम संख्या में स्वैप खोजने का कार्यक्रम

मान लीजिए कि हमारे पास पंक्ति नामक संख्याओं की एक सूची है और यह एक पंक्ति में पड़े मोज़े का प्रतिनिधित्व कर रहा है। उन्हें क्रमबद्ध नहीं किया गया है, लेकिन हम उन्हें पुनर्व्यवस्थित करना चाहते हैं ताकि मोजे की प्रत्येक जोड़ी अगल-बगल हो जैसे (0, 1), (2, 3), (4, 5), और इसी तरह। हमें उन्हें पुनर्व्यवस्थित करने के लिए आवश्यक न्यूनतम संख्या में स्वैप का पता लगाना होगा।

इसलिए, यदि इनपुट पंक्ति =[0, 5, 6, 2, 1, 3, 7, 4] की तरह है, तो आउटपुट 2 होगा, क्योंकि पंक्ति के आदेश हैं

• [0, 5, 6, 2, 1, 3, 7, 4]

• [0, 1, 6, 2, 5, 3, 7, 4]

• [0, 1, 3, 2, 5, 6, 7, 4]

• [0, 1, 3, 2, 5, 4, 7, 6]

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

• एक सरणी p और दूसरी सरणी sz परिभाषित करें

• फ़ंक्शन ढूंढें () को परिभाषित करें, यह आपको ले जाएगा,

• वापसी (यदि पी [यू] यू के समान है, तो यू, अन्यथा ढूंढें (पी [यू]) और पी [यू]:=ढूंढें (पी [यू]))

• फंक्शन जॉइन () को परिभाषित करें, इसमें आपको, वी,

  . लगेगा

• पु:=ढूंढें ((यू), पीवी:=ढूंढें (वी))

• यदि PU, pv के समान है, तो -

  • वापसी

• अगर sz[pu]>=sz[pv], तो -

  • पी[पीवी] :=पु

  • sz[पु] :=sz[पु] + sz[pv]

• अन्यथा

  • पी[पु] :=पीवी

  • sz[pv] :=sz[pv] + sz[पु]

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

• n :=गिरफ्तारी का आकार

• p :=आकार की एक सरणी n

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

  • पी[i] :=मैं

• sz :=आकार n की एक सरणी और 1 से भरें

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

  • आप :=एआर [i/2] / 2

  • v :=arr[(i/2) OR 1] / 2

  • शामिल हों (यू, वी)

• उत्तर :=0

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

  • यदि खोज (i) i के समान है, तो -

    • उत्तर :=उत्तर + sz[i] − 1

  • वापसी उत्तर

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int find(int u) {
   return p[u] == u ? u : p[u] = find(p[u]);
}
void join(int u, int v) {
   int pu = find(u), pv = find(v);
   if (pu == pv)
   return;
   if (sz[pu] >= sz[pv]) {
      p[pv] = pu;
      sz[pu] += sz[pv];
   }else {
      p[pu] = pv;
      sz[pv] += sz[pu];
   }
}
int solve(vector<int>& arr) {
   int n = arr.size() / 2;
   p = vector<int>(n);
   for (int i = 0; i < n; ++i)
   p[i] = i;
   sz = vector<int>(n, 1);
   for (int i = 0; i < n; ++i) {
      int u = arr[i << 1] / 2;
      int v = arr[i << 1 | 1] / 2;
      join(u, v);
   }
   int ans = 0;
   for (int i = 0; i < n; ++i)
   if (find(i) == i)
   ans += sz[i] − 1;
   return ans;
}
int main(){
   vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
   cout << solve(v);
}

इनपुट

{2, 4, 6, 3}

आउटपुट

23