fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define PB push_back
  5. #define FI first
  6. #define SE second
  7. #define MP make_pair
  8. #define ALL(cont) cont.begin(), cont.end()
  9. #define MOD 1000000007ll
  10. #define SIZE 500100
  11.  
  12. ll arr[SIZE];
  13. ll par[SIZE];
  14. bool indegree[SIZE];
  15. ll ans[SIZE];
  16. ll idx;
  17.  
  18. void dfs(ll nd)
  19. {
  20.     ans[nd] = idx++;
  21.     if(arr[par[nd]]!=-1)
  22.         dfs(par[nd]);
  23. }
  24.  
  25.  
  26. int main()
  27. {
  28.     ios::sync_with_stdio(0);
  29.     cin.tie(0);cout.tie(0);
  30. #ifndef ONLINE_JUDGE
  31.     freopen("input.txt", "r", stdin);
  32.     freopen("output.txt", "w", stdout);
  33. #endif
  34.  
  35.  
  36.     for(int i=0;i<SIZE;i++)
  37.     {
  38.         par[i] = -1;
  39.         indegree[i] = false;
  40.     }
  41.  
  42.  
  43.     ll N;
  44.     cin>>N;
  45.     for(ll i=1;i<=N;i++)
  46.     {
  47.         cin>>arr[i];
  48.         par[i] = arr[i];
  49.         indegree[arr[i]] = true;
  50.     }
  51.  
  52.     idx = 1;
  53.  
  54.     for(int i=1;i<=N;i++)
  55.     {
  56.         if(indegree[i]==false)
  57.         {
  58.             // cout<<"call on: "<<i<<endl;
  59.             dfs(i);
  60.         }
  61.     }
  62.  
  63.     for(ll i=N;i>0;i--)
  64.     {
  65.         if(arr[i]==-1)
  66.             ans[i] = idx++;
  67.     }
  68.  
  69.     for(ll i=1;i<=N;i++)
  70.         cout<<ans[i]<<" ";
  71.  
  72.  
  73.  
  74.     return 0;
  75.  
  76.  
  77. }
Success #stdin #stdout 0s 7856KB
comments (?)
stdin
copy 
6
2 -1 1 5 -1 4
stdout
copy 
2 6 1 4 5 3
https://ideone.com/tlFokV
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!