E - Minimum Swap Editorial by en_translator
First, consider the number of operations required to make \(P\) equal to \((1,2,\ldots,N)\), which we will denote by \(K\).
For a permutation \(P\) of \((1,2,\ldots,N)\), consider a graph with \(N\) vertices: vertex \(1\), vertex \(2,\ldots,) and vertex \(N\). For each \(i=1,2,\ldots,N\), add an edge connecting vertices \(i\) and \(P _ i\). We claim that \(K=N-C\), where \(C\) is the number of connected component in this graph.
Proof
Every connected component is a cycle of size \(1\) or greater. Pick a vertex from each connected component; denote them as \(i _ 1,i _ 2,\ldots,i _ C\). Then each cycle is represented as \(i _ k,P _ {i _ k},P _ {P _ {i _ k}},\ldots\ (1\le k\le C)\).
Consider what happens to \(C\) if you perform an operation on \((i,j)\). We split into cases depending on whether vertices \(i\) and \(j\) are in the same connected component.
If vertices \(i\) and \(j\) are in the same connected component, the original cycle \((i,P _ i,P _ {P _ i},\ldots,j,P _ j,P _ {P _ j},\ldots,P ^ {-1} _ i)\ \bigl(\) (where \(P ^ {-1} _ i\) denotes the integer \(x\) such that \(P _ x=i\)) is transformed by the operation into two cycles, \((P _ i,P _ {P _ i},\ldots,j)\) and \((P _ j,P _ {P _ j},\ldots,i)\). Therefore, in this case \(C\) is increased by one.
If vertices \(i\) and \(j\) are in different connected components, the original two cycles \((i,P _ i,P _ {P _ i},\ldots,P ^ {-1} _ i)\) and \((j,P _ j,P _ {P _ j},\ldots,P ^ {-1} _ j)\) are transformed by the operation into a cycle \((j,P _ i,P _ {P _ i},\ldots,i,P _ j,P _ {P _ j},\ldots,P ^ {-1} _ j)\). Therefore, in this case \(C\) is decreased by one.
We have \(N=C\) if and only if \(P\) is equal to \((1,2,\ldots,N)\). If \(N\gt C\), there always exist two vertices that are contained in the same connected component (indeed, \((i,P _ i)\) with \(i\ne P _ i\) satisfies satisfies the condition). Thus, one can always increase \(C\) by one as long as \(N\gt C\). Conversely, \(C\) is increased by at most one by an operation. Hence it has been shown that \(K=N-C\).
By the discussion above, it turns out that one has to perform \(K\) times the operation of choosing two vertices in the same connected component (in the graph corresponding to \(P\) at the point of performing the operation). We also see that any two vertices may be chosen as long as they belong to the same connected component.
Therefore, the problem has been solved in \(O(N)\) time by finding the size of each connected component.
The following is sample code.
#include <iostream> #include <vector> #include <ranges> #include <numeric> int main() { using namespace std; unsigned N; cin >> N; vector<unsigned> P(N); for (auto&& p : P) { cin >> p; --p; } vector<unsigned> ans(N); for (const auto i : views::iota(0U, N)) if (!ans[i]) { auto p{i}; unsigned count{}; do { ++count; p = P[p]; } while (p != i); // detect a cycle do { ans[p] = count; // and record the size of the cycle that the vertex belongs p = P[p]; } while (p != i); } cout << (reduce(begin(ans), end(ans), 0UL) - N) / 2 << endl; return 0; } posted:
last update: