#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define fastOI ios_base::sync_with_stdio(false); \
cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
vector<int> test;
vector<int> visited;
int n;
void dfs(int u){
visited[u] = 1;
if(visited[test[u]] == 1)return;
dfs(test[u]);
return;
}
vector<pair<int,int>> pairstodo;
void dfspair(int u, int v){
visited[u] = 1;
if(u != v){
pairstodo.push_back({u, v});
}
if(visited[test[u]] == 1)return;
dfspair(test[u], u);
return;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int mini = 0;
n = N;
vector<int> start;
for(int i =0; i<N; i++){
start.push_back(S[i]);
}
test = start;
for(int i =0; i<=N; i++){
if(i != 0)swap(test[X[i-1]], test[Y[i-1]]);
//for(auto k : test)cout<<k<<" ";
visited.assign(n, 0);
int counter = n;
for(int j =0; j<n; j++){
if(visited[j] == 1)continue;
counter--;
dfs(j);
}
//cout<<counter<<"\n";
if(counter <= i){
mini = i;
break;
}
}
//cout<<mini<<" ";
//for(auto k : test)cout<<k<<" ";
//cout<<"\n";
visited.assign(n, 0);
for(int i =0; i<n; i++){
if(visited[i] == 1)continue;
dfspair(i, i);
}
//for(auto k : pairstodo)cout<<k.first<<" "<<k.second<<"\n";
vector<int> posholder(n);
for(int i =0; i<n; i++){
posholder[start[i]] = i;
pairstodo.push_back({0,0});
}
test = start;
for(int i =0; i<mini; i++){
posholder[test[X[i]]] = test[Y[i]];
posholder[test[Y[i]]] = test[X[i]];
swap(test[X[i]], test[Y[i]]);
P[i] = posholder[pairstodo[i].first];
Q[i] = posholder[pairstodo[i].second];
}
//cout<<mini<<"\n";
//for(int i =0; i<mini; i++)cout<<P[i]<<" "<<Q[i]<<"\n";
return mini;
}
Compilation message
horses.cpp:1:10: fatal error: sorting.h: No such file or directory
1 | #include "sorting.h"
| ^~~~~~~~~~~
compilation terminated.
