Description

牛客幼儿园的小朋友课间操时间需要按照学号从小到大排队，但是他们太小了只能站成一列顺序却不对，现在幼儿园的阿姨需要帮忙交换小朋友的位置让他们最终有序，阿姨希望能尽快完成交换操作，问最少需要交换多少次，才能使得小朋友们从小到大排好。
注意：每个小朋友的学号不同，但是未必连续，因为可能有小朋友请假了没有来。

Solution

这道题有点意思, 一开始以为是求逆序数, 但是仔细一看他跟我们之前求的最小交换数的条件有所不同
简单的说，这道题不限定交换的是相邻两个，因此我们可以自由交换
我们可以推断出有一个循环节，就可以少交换一次，因为n个元素的循环节，只需交换n-1次即可有序。
那么对于整个序列来说，最少交换次数为 元素总数-循环节个数。
那么就是个结论题，结论是 数字个数 - 循环节的个数
什么是循环节呢？我们知道每一个数字都有他们应该所在的位置和当前的位置
比如 a 应该放在 b, b 要放在 c..... 这样一直循环下去直到有一个数字的位置放在我们找过的位置中
即会形成一个环, 显然我们可以当成图论题来做了，对于每个点, 如果所在位置不是它应该处在的位置
那么我们对当前位置和应处位置建边，最后会形成一个图
我们在图上dfs找有多少个环即可

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;

int a[N], b[N], cnt;
bool vis[N];
vector<int> G[N];
void addedge(int u, int v) {
  G[u].push_back(v), G[v].push_back(u);
}
void dfs(int x) {
  for(int i = 0; i < G[x].size(); i++) {
    int v = G[x][i];
    if(!vis[v]) {
      vis[v] = 1;
      dfs(v);
    }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i];
  }
  sort(b + 1, b + 1 + n);
  map<int, int> mp;
  for(int i = 1; i <= n; i++) {
    mp[b[i]] = i; // 应该在的位置
  }
  for(int i = 1; i <= n; i++) {
    if(a[i] != b[i]) {
      addedge(i, mp[a[i]]);
      addedge(mp[a[i]], i);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    if(!vis[i]) {
      vis[i] = 1;
      ans++;
      dfs(i);
    }
  }
  cout << n - ans << "\n";
  return 0;
}