最小的是找联通块数 最大的找环 一个环算一个 其它的数各算一个
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 using namespace std; 8 #define N 100010 9 int fa[N],vis[N]; 10 int minz,maxz,de[N],f[N],pp[N]; 11 void dfs(int u,int v) 12 { 13 de[u] = v; 14 vis[u] = 1; 15 f[v] = u; 16 int i; 17 if(vis[fa[u]]) 18 { 19 for(i = v; i >= 1 ; i--) 20 if(f[i]==fa[u]) 21 break; 22 if(i>0) 23 maxz+=v-(de[u]-de[fa[u]]); 24 else 25 maxz+=v; 26 return ; 27 } 28 dfs(fa[u],v+1); 29 } 30 void dfs1(int u) 31 { 32 vis[u]=1; 33 if(!vis[fa[u]]) 34 dfs1(fa[u]); 35 else 36 return ; 37 } 38 int main() 39 { 40 int i,n; 41 scanf("%d",&n); 42 for(i = 1; i <= n ; i++) 43 { 44 scanf("%d",&fa[i]); 45 pp[fa[i]] = 1; 46 } 47 for(i = 1; i <= n ;i++) 48 { 49 if(!vis[i]&&pp[i]==0) 50 { 51 minz++; 52 dfs(i,1); 53 } 54 } 55 for(i = 1; i <= n ; i++) 56 { 57 if(!vis[i]) 58 { 59 minz++; 60 maxz++; 61 dfs1(i); 62 } 63 } 64 printf("%d %d ",minz,maxz); 65 return 0; 66 }