fork download 
  1. #include <bits/stdc++.h>
  2. #define ll int
  3. #define FOR(index, lower, upper) for (ll index = lower; index < upper; index++)
  4. using namespace std;
  5. void solve(ll);
  6. void io() {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(NULL);
  9.     cout.tie(NULL);
  10. }
  11. int main() {
  12.     io();
  13. #ifndef ONLINE_JUDGE
  14.     freopen("input", "r", stdin);
  15.     freopen("output", "w", stdout);
  16. #endif
  17.     ll T = 1ll;
  18.     // cin >> T;
  19.     FOR(i, 1, T + 1) {
  20.         solve(i);
  21.     }
  22. }
  23. ll n;
  24. vector<ll> vc;
  25. ll size_of_cycle = 0;
  26. vector<ll> ans;
  27. void dfs(ll node, vector<ll> &vc, vector<bool> &part_of_cycle, vector<ll> &ans) {
  28.     if (part_of_cycle[node]) {
  29.         ans[node] = size_of_cycle;
  30.         return;
  31.     }
  32.     dfs(vc[node], vc, part_of_cycle, ans);
  33.     ans[node] = ans[vc[node]] + 1;
  34. }
  35. void helper(ll src) {
  36.     ll hare = src, tortoise = src;
  37.     vector<bool> visited(n + 1, false);
  38.     visited[hare]=true;
  39.     do{
  40.         hare = vc[vc[hare]];
  41.         tortoise = vc[tortoise];
  42.         visited[hare] = true;
  43.         visited[tortoise] = true;
  44.     }while (hare != tortoise); 
  45.     tortoise = src;
  46.     while (hare != tortoise) {
  47.         hare = vc[hare];
  48.         tortoise = vc[tortoise];
  49.         visited[hare] = true;
  50.         visited[tortoise] = true;
  51.     }
  52.     ll t = hare;
  53.     vector<bool> part_of_cycle(n + 1, false);
  54.     size_of_cycle=0;
  55.     do {
  56.         part_of_cycle[t] = true;
  57.         t = vc[t];
  58.         size_of_cycle++;
  59.     } while (t != hare);
  60.     FOR(i, 1, n + 1) {
  61.         if (ans[i] == -1 && visited[i]) {
  62.             dfs(i, vc, part_of_cycle, ans);
  63.         }
  64.     }
  65. }
  66. void solve(ll TC) {
  67.     cin >> n;
  68.     vc.resize(n+1);
  69.     FOR(i,1,n+1){
  70.         cin>>vc[i];
  71.     }
  72.     ans.resize(n + 1, -1);
  73.     FOR(i, 1, n + 1) {
  74.         if (ans[i] == -1)
  75.             helper(i);
  76.     }
  77.     FOR(i,1,n+1)cout<<ans[i]<<" ";
  78. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/jfQlc9
language:
C++ (gcc 8.3)
created:
2 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!