fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD= 1e9+7;
  5. const int N= 1e6+1;
  6. int f[N],depth[N],vis[N];
  7. long long int ans=1;
  8. int n,k;
  9. int dfs(int node)
  10. {
  11.     if(vis[node])
  12.     {
  13.         if(depth[node]==-1)
  14.           return k;
  15.         else
  16.             return (depth[node]-1);
  17.     }
  18.  
  19.     else{
  20.         vis[node]=1;
  21.         if(f[node]==node)
  22.         {
  23.             depth[node]=k;
  24.             ans*=k;
  25.             ans%=MOD;
  26.             return (depth[node]-1);
  27.         }
  28.         else
  29.         {
  30.           depth[node] = dfs(f[node]);
  31.            // cout<<node<<" "<<depth[node]<<endl;
  32.       	  ans*=depth[node];
  33.           ans%=MOD;
  34.           return (depth[node]-1);
  35.         }
  36.  
  37.     }
  38. }
  39. int main() {
  40.  
  41.     cin>>n>>k;
  42.  
  43.  
  44.  
  45.     for(int i=1;i<=n;i++)
  46.         cin>>f[i],depth[i]=-1,vis[i]=0;
  47.  
  48.     for(int i=1;i<=n;i++)
  49.     {
  50.         int st=i;
  51.         while(!vis[st])
  52.         {
  53.             dfs(st);
  54.         }  
  55.     }
  56.     cout<<ans;
  57.     return 0;
  58. }
Success #stdin #stdout 0.01s 5412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Mbki4p
3 4
2 3 1
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!