Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n;
- int points_to[50005];
- int value[50005];
- bool visited[50005];
- bool visited_its[50005];
- bool in_loop[50005];
- void set_loop(int start)
- {
- unordered_set<int> vis_loop;
- int current = start;
- while(vis_loop.find(current) == vis_loop.end()){
- in_loop[current] = true;
- vis_loop.insert(current);
- current = points_to[current];
- }
- int siz = vis_loop.size();
- for(auto vis : vis_loop){
- value[vis] = siz - 1;
- }
- }
- int dfs(int current)
- {
- visited[current] = true;
- visited_its[current] = true;
- if(visited_its[points_to[current]]){
- set_loop(current);
- return value[current];
- }
- dfs(points_to[current]);
- if(in_loop[current]){
- return value[current];
- }
- else{
- value[current] = value[points_to[current]] + 1;
- return value[current];
- }
- }
- int main()
- {
- int b;
- cin>>n;
- memset(visited, 0, sizeof(visited));
- memset(in_loop, 0, sizeof(in_loop));
- memset(value, 0, sizeof(value));
- for(int i = 0; i < n; i++){
- points_to[i] = -1;
- }
- for(int i = 0; i < n; i++){
- cin>>b;
- points_to[i] = b-1;
- }
- for(int i = 0; i < n; i++){
- if(!visited[i]){
- memset(visited_its, 0, sizeof(visited_its));
- dfs(i);
- }
- }
- int ans_val = -1;
- for(int i = 0; i < n; i++){
- ans_val = max(ans_val, value[i]);
- }
- cout<<ans_val + 1<<"\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment