Josif_tepe

Untitled

Sep 16th, 2025
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n;
  6. int points_to[50005];
  7. int value[50005];
  8. bool visited[50005];
  9. bool visited_its[50005];
  10. bool in_loop[50005];
  11.  
  12. void set_loop(int start)
  13. {
  14.     unordered_set<int> vis_loop;
  15.     int current = start;
  16.     while(vis_loop.find(current) == vis_loop.end()){
  17.         in_loop[current] = true;
  18.         vis_loop.insert(current);
  19.         current = points_to[current];
  20.     }
  21.     int siz = vis_loop.size();
  22.     for(auto vis : vis_loop){
  23.         value[vis] = siz - 1;
  24.     }
  25. }
  26.  
  27. int dfs(int current)
  28. {
  29.     visited[current] = true;
  30.     visited_its[current] = true;
  31.     if(visited_its[points_to[current]]){
  32.         set_loop(current);
  33.         return value[current];
  34.     }
  35.     dfs(points_to[current]);
  36.     if(in_loop[current]){
  37.          return value[current];
  38.     }
  39.     else{
  40.         value[current] = value[points_to[current]] + 1;
  41.         return value[current];
  42.     }
  43. }
  44.  
  45. int main()
  46. {
  47.     int b;
  48.     cin>>n;
  49.     memset(visited, 0, sizeof(visited));
  50.     memset(in_loop, 0, sizeof(in_loop));
  51.     memset(value, 0, sizeof(value));
  52.     for(int i = 0; i < n; i++){
  53.         points_to[i] = -1;
  54.     }
  55.     for(int i = 0; i < n; i++){
  56.         cin>>b;
  57.         points_to[i] = b-1;
  58.     }
  59.     for(int i = 0; i < n; i++){
  60.         if(!visited[i]){
  61.             memset(visited_its, 0, sizeof(visited_its));
  62.             dfs(i);
  63.         }
  64.     }
  65.     int ans_val = -1;
  66.     for(int i = 0; i < n; i++){
  67.         ans_val = max(ans_val, value[i]);
  68.     }
  69.     cout<<ans_val + 1<<"\n";
  70.  
  71.     return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment