Какого минимума нет. свопов для сортировки этого массива - PullRequest
0 голосов
/ 04 мая 2020

Что минимум нет. из swaps для сортировки этого массива длины n, если у нас есть несколько m запросов. В m запросах мы можем поменять 2 позиции, и это не будет включено в минимальные свопы. Значения массива представляют собой непрерывные числа в диапазоне от 1 до n в зависимости от размера, если n = 3, nos равны 1,2,3, но могут быть расположены в любом порядке. Подобно nm A1, A2, ..., An m запросов, 1 < = n <= 100,0 <= m <= 100 </p>

Input:-
3 1
2 1 3
0 1

Выход: - 1

Код: -

 #include <iostream>
#include<bits/stdc++.h> 
using namespace std;

vector<int>v[100];
bool visit[100];


int dfs(int i)
{
    visit[i] = true;
    int z = 1;

    for(auto x: v[i])
        if(!visit[x])
            z += dfs(x);

    return z;  
}


int minimumSwaps(vector<int> A) {

    for(int i = 0; i < A.size(); ++i )
        v[i].push_back(A[i]-1), v[A[i]-1].push_back(i);

    int c = 0;

    for(int i = 0; i < A.size(); ++i)
    {
        if(!visit[i])
            c += dfs(i) - 1;
    }

    return c;
}

int main() {
    // your code goes here


      int n , m ;
      cin>>n>>m;
      vector<int> vect;
      for(int i=0 ; i<n;i++){
          cin>>vect[i];
      }

      int a,b;
      for(int k = 0 ; k<m;k++){
          cin>>a>>b;
          if(vect[a]>vect[b]){
              swap(vect[a],vect[b]);
          }
      }

      int sum =  minimumSwaps(vect);
        cout<<sum<<endl;


    return 0;
}
...