1.递归求解  注：叙述时 节点其实就是数字0-N-1 

！！！最好用一个数组记录0-N-1每个数字的位置

！！！递归计算一个置换群内部的节点数 分为两种情况 累加M，M即是一个置换群所有数字在正确位置上所需要的swap 次数。这句话

需要详细解释下，如果这个置换群里面有0则M=置换群节点数量-1（找一个测试样例，自行模拟）;如果这个置换群里面没有0，则M=置换群节点数量+1

！！！vis记录是否该节点已经被放在正确的位置

！！！剩下就没什么可说的了 参考了https://www.cnblogs.com/biaobiaoqi/p/3357228.html

#include <iostream>

using namespace std;

int arr[100000+5];

bool vis[100000+5]={0};

bool zero;

int M;//循环链节点个数

int cnt=0;//交换次数

void dfs(int v){

if(v!=0&&vis[v]){

return;

}

if (v==0)

zero=1;

vis[v]=1;

M++;

//cout<<M<<"***"<<zero<<endl;

dfs(arr[v]);

}

int main(){

int N,temp,ans=0,num=0;

scanf("%d",&N);

for (int i=0;i<N;i++){

scanf("%d",&temp);

arr[temp]=i;

}

for (int i=0;i<N;i++){

zero=0;

M=0;

if (i!=0&&!vis[i]&&arr[i]!=i){

dfs(i);

if (zero==1){

cnt+=M-1;

}

else{

cnt+=M+1;

}

}

}

cout<<cnt;

}

 

2.并查集 先欠着 后续再说 （其实能解决是解决 ，感觉递归计算更直观）