题目
松鼠排序
n个不同的数，任意交换位置进行排序，其最小交换次数。
思路
结论：\(最小交换次数=n - r\)，其中\(r\)为置换环个数。
参考：https://www.cnblogs.com/CDOI-24374/p/16410082.html
代码
Code
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;
vector<int> adj[N];
bool vis[N];
void dfs(int u)
{
vis[u] = true;
for (auto v: adj[u]) if (!vis[v]) dfs(v);
}
void solv()
{
int n;
cin >> n;
for (int i = 1, a; i <= n; i ++)
{
cin >> a;
adj[a].push_back(i);
}
int cnt = 0;
for (int i = 1; i <= n; i ++)
if (!vis[i])
{
cnt ++;
dfs(i);
}
cout << n - cnt << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solv();
}
return 0;
}