Consider a graph \(G\) with \(N\) vertices and \(N\) edges \((i,P_{i})\). We assume that \(G\) changes as \(P\) changes.

Let \(C\) be the number of connected components. If \(P\) is a good permutation, then \(C=1\). When \(C\neq 1\), there are \(i\) and \(j\) such that swapping \(P_{i},P_{j}\) reduces \(C\) by exactly \(1\), so \(M=C-1\).

We should proceed as follows for \(i=1,2,\dots N\) in this order.

• Choose the smallest \(a\) for which there is a good permutation that can be achieved in \(M\) operations with \(P_{i}=a\). Then, if \(P_{i}\neq a\), let \(b\) be the integer such that \(b=P_{a}\), swap \(P_{i}\) and \(P_{b}\), and decrease \(M\) by \(1\).

Here, \(a\) will be chosen to be \(P_{i}\) or the value \(r\) defined as follows:

• the smallest integer \(2\leq j\leq N\) such that vertices \(j-1\) and \(j\) of \(G\) belong to different connected components.

\(r\) will be chosen as \(a\) only if one of the following two conditions is satisfied:

• \(r\lt P_{i}\).
• \(i=r-1\), and \(P_{j}\lt r\) for every integer \(j\) such that \(1\leq j\leq i\).

Thus, after finding \(a\) each time \(M\) decreases by \(1\), we should calculate the smallest \(i\) that satisfies either of the above two conditions.

Taking advantage of the fact that \(i\) and \(a\) are both monotonically increasing, we can implement a solution that runs in time complexity \(O(N)\) or \(O(N\alpha (N))\).