1 #include <cstdio>  2 #include <cstring>  3 #include <cmath>  4 #include <iostream>  5 #include <algorithm>  6 #include <map>  7 #include <vector>  8 #include <queue>  9 using namespace std; 10 #define EPS 1e-10 11 typedef long long ll; 12 const int maxn = 2e5 + 10; 13 const int INF = 1e9 ; 14 const int N = maxn; 15 const int M = maxn; 16  17 struct Edge { 18     int to, next; 19 } edge[M*2]; 20 int head[N]; 21 int cnt_edge; 22  23 void add_edge(int u, int v) 24 { 25     edge[cnt_edge].to = v; 26     edge[cnt_edge].next = head[u]; 27     head[u] = cnt_edge; 28     cnt_edge++; 29 } 30 vector<int>q; 31 int dfn[N]; 32 int low[N]; 33 int stk[N]; 34 bool in[N]; 35 int kind[N]; 36  37 int top; 38 int idx; 39 int cnt; 40  41 int n, m,num; 42  43 void dfs(int u) 44 { 45     dfn[u] = low[u] = ++idx; 46     in[u] = true; 47     stk[++top] = u; 48     for (int i = head[u]; i != -1; i = edge[i].next) 49     { 50         int v = edge[i].to; 51         if (!dfn[v]) 52         { 53             dfs(v); 54             low[u] = min(low[v], low[u]); 55         } 56         else if(in[v]) 57         { 58             low[u] = min(low[u], dfn[v]); 59         } 60     } 61  62     if (low[u] == dfn[u]) 63     { 64         ++cnt; 65         int j; 66         num = 0; 67         do { 68             num++; 69             j = stk[top--]; 70             in[j] = false; 71             kind[j] = cnt; 72         } while (j != u); 73         if(num > 1) 74         q.push_back(stk[top+1]); 75     } 76 } 77  78 void init() 79 { 80     memset(dfn, 0, sizeof dfn); 81     memset(head, -1, sizeof head); 82     cnt_edge = 0; 83     top = cnt = idx = 0; 84 } 85 int main(){ 86    // freopen("in.txt","r",stdin); 87     cin>>n; 88     int a[maxn]; 89     init(); 90     int cnt = 0; 91     for(int i = 1;i <= n;i++){ 92         scanf("%d",&a[i]); 93         if(i != a[i]){ 94             add_edge(i,a[i]); 95         } 96         else{ q.push_back(i); 97             cnt = 1; 98         } 99     }100 101     for(int i = 1;i <= n;i++){102     if(!dfn[i]){103         dfs(i);104     }105     }106 107     if(num == n){108         cout<<1<<endl;109         a[q[0]] = q[0];110         for(int i = 1;i <= n;i++)111             if(i == n) printf("%d\n",a[i]);112             else printf("%d ",a[i]);113     }114     else{115         if(cnt)116             cout<<q.size() - 1<<endl;117         else118             cout<<q.size()<<endl;119         for(int i = 0;i < q.size();i++)120             a[q[i]] = q[0];121         for(int i = 1;i <= n;i++){122             if(i == n) printf("%d\n",a[i]);123             else printf("%d ",a[i]);124         }125     }126     return 0;127 }