#include "sorting.h"
#include <algorithm>
#include <vector>
const int MAXN = 2e5;
int perm[MAXN];
bool seen[MAXN];
std::vector<int> left;
std::vector<int> right;
int reversePerm[MAXN];
void setup(int swaps, int permSize, int initPerm[], int swapLeft[], int swapRight[])
{
for (int iPos = 0; iPos < permSize; iPos++)
{
perm[iPos] = initPerm[iPos];
seen[iPos] = false;
}
for (int iSwap = 0; iSwap < swaps; iSwap++)
std::swap(perm[swapLeft[iSwap]], perm[swapRight[iSwap]]);
}
bool floodfill(int pos)
{
if (seen[pos])
return false;
seen[pos] = true;
floodfill(perm[pos]);
return true;
}
int countcycles(int permSize)
{
int cycles = 0;
for (int iPos = 0; iPos < permSize; iPos++)
cycles += floodfill(iPos);
return cycles;
}
bool createpairs(int pos)
{
if (seen[pos])
return false;
seen[pos] = true;
if (createpairs(perm[pos]))
{
left.emplace_back(perm[pos]);
right.emplace_back(perm[perm[pos]]);
}
return true;
}
int minswaps(int lower, int upper, int permSize, int initPerm[], int swapLeft[], int swapRight[])
{
if (lower == upper)
return upper;
int swaps = (lower + upper) / 2;
setup(swaps, permSize, initPerm, swapLeft, swapRight);
if (permSize - countcycles(permSize) <= swaps)
return minswaps(lower, swaps, permSize, initPerm, swapLeft, swapRight);
return minswaps(swaps + 1, upper, permSize, initPerm, swapLeft, swapRight);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
int requiredSwaps = minswaps(0, M, N, S, X, Y);
int answer = requiredSwaps;
setup(requiredSwaps, N, S, X, Y);
for (int iPos = 0; iPos < N; iPos++)
{
createpairs(iPos);
reversePerm[perm[iPos]] = iPos;
}
while ((int)left.size() < requiredSwaps)
{
requiredSwaps--;
P[requiredSwaps] = Q[requiredSwaps] = 0;
std::swap(perm[X[requiredSwaps]], perm[Y[requiredSwaps]]);
std::swap(reversePerm[perm[X[requiredSwaps]]], reversePerm[perm[Y[requiredSwaps]]]);
}
while (requiredSwaps > 0)
{
requiredSwaps--;
P[requiredSwaps] = reversePerm[left[requiredSwaps]];
Q[requiredSwaps] = reversePerm[right[requiredSwaps]];
std::swap(perm[X[requiredSwaps]], perm[Y[requiredSwaps]]);
std::swap(reversePerm[perm[X[requiredSwaps]]], reversePerm[perm[Y[requiredSwaps]]]);
}
return answer;
}
