题目链接：https://codeforces.com/problemset/problem/1768/D
知识：置换环，并查集
并且可以发现一个结论（可以自己画几个环图感受一下）：
交换环内两个元素的位置，会将大环拆成小环。
交换两个环的两个元素的的位置，会将小环变成大环。
思路：最终要达成的序列为单元排列并且其中的两个数字交换位置。我们可以将num[i]和i连一条边。然后并查集维护环，如果存在一个环，它其中的环内元素有两个相邻数字时，那么答案需要减一，否则答案需要加一。
答案为将所有环拆成只有一个数字构成的环所需要的操作数。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int num[N];
int p[N],sz[N];
set<int>S;
int find(int x){
if (x!=p[x]) p[x] = find(p[x]);
return p[x];
}
void solve(){
int n;
cin>>n;
S.clear();
for (int i=1;i<=n;i++) cin>>num[i];
for (int i=1;i<=n;i++) p[i] = i,sz[i] = 1;
for (int i=1;i<=n;i++){
int x = find(num[i]);
int y = find(i);
if (x!=y){
sz[y] += sz[x];
p[x] = y;
}
}
int flag = 1;
for (int i=1;i<=n;i++){
int x = find(i);
S.insert(x);
if (i<n){
if (find(i)==find(i+1)) flag = -1;
}
}
int ans = 0;
for (auto s:S){
if (sz[s]) ans += (sz[s]-1);
}
cout<<ans+flag<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
cin>>T;
while(T--) solve();
return 0;
}