Что минимум нет. из 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;
}