dfs找出联通块个数cnt，当形成环时，令指向已访问过节点的节点变成指向-1，即做一个标记。把它作为该联通图的根。

把所有联通的图变成一颗树，如果存在指向自己的点，那么它所在的联通块就是一个树（n-1条边），选择这样一个点，其它联通块的根指向它，就需要cnt-1次改变。如果都是环（没有指向自己的），那任意选定一个环，拆开，其它环拆开再连到此环上，就需要cnt次改变。

#include 
     
      #define N 200005int a[N],v[N],h[N],fa[N],q[N],ans,cnt,ba;int dfs(int u){    v[u]=cnt;    if(!v[a[u]])return a[u]=dfs(a[u])==-1?a[u]:a[a[u]];    if(v[a[u]]==cnt&&a[u]!=u)return a[u]=-1;//指向的是本次dfs内访问的点，即形成环    return a[u]=a[a[u]]==-1?a[u]:a[a[u]];//可能是-1即是前面的拆环点}int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        fa[i]=a[i];        if(a[i]==i)ba=i;    }    for(int i=1;i<=n;i++)    if(!v[i]){        cnt++;//第cnt次dfs        dfs(i);        if(++h[a[i]]==1)            ans++;//联通块个数    }    printf("%d\n",ans-(ba>0));    for(int i=1;i<=n;i++)        //拆环点（-1），或者不是总根的树根，是需要改变的。        if(a[i]==-1||i==a[i]&&i!=ba)printf("%d ",ba?ba:ba=i);//ba为0则选定i为总的根。        else printf("%d ",fa[i]);//不改变}