fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n;
  10. 	cin >> n;
  11. 	vector<vector<int>> g(n + 1, vector<int>());
  12. 	vector<int> in_degree(n + 1, 0);
  13. 	for(int i = 0; i < n; i++){
  14. 		int x;
  15. 		cin >> x;
  16. 		g[i + 1].push_back(x);
  17. 		in_degree[x]++;
  18. 	}
  19.  
  20. 	int last = 1;
  21. 	vector<int> visited(n + 1, 0);
  22. 	int ans = 2;
  23. 	int t = 1;
  24. 	auto dfs = [&](int x, auto && self) -> void {
  25. 		last = x;
  26. 		if(visited[x]) {
  27. 			return;
  28. 		}
  29.  
  30. 		visited[x] = t;
  31. 		for(auto y: g[x]){
  32. 			self(y, self);
  33. 		}
  34. 	};
  35.  
  36. 	vector<int> visited2(n + 1, 0);
  37. 	auto dfs1 = [&](int x, auto && self) -> void {
  38. 		if(visited2[x])return;
  39. 		visited2[x] = 1;
  40. 		for(auto y: g[x]){
  41. 			self(y, self);
  42. 		}
  43. 	};
  44.  
  45.  
  46. 	for(int i = 1; i <= n; i++){
  47. 		if(in_degree[i] == 0 && !visited[i]){
  48. 			dfs(i, dfs);
  49. 			if(visited[last] == t)dfs1(last, dfs1);
  50. 			t++;
  51. 		}
  52. 	}
  53.  
  54. 	visited = visited2;
  55.  
  56. 	queue<int> q;
  57.  
  58. 	vector<int> times(n + 1, 0);
  59. 	vector<int> pulses(n + 1, 1);
  60. 	for(int i = 1; i <= n; i++){
  61. 		if(in_degree[i] == 0){
  62. 			times[i] = 1;
  63. 			q.push(i);
  64. 		}
  65. 	}
  66.  
  67. 	while(q.size()){
  68. 		auto x = q.front();
  69. 		q.pop();
  70. 		// cout << x << "\n";
  71.  
  72. 		for(auto z: g[x]){
  73. 			in_degree[z]--;
  74. 			times[z] = max(times[z], max(times[x] + 1, pulses[x] + 1));
  75. 			pulses[z] += pulses[x];
  76. 			if(!visited[z] && in_degree[z] == 0)q.push(z);
  77. 			if(visited[z]){
  78. 				ans = max(ans, times[z] + 1);
  79. 			}
  80. 		}
  81. 	}
  82.  
  83.  
  84. 	cout << ans << "\n";
  85. }
  86.  
  87. int main(){
  88. 	ios_base::sync_with_stdio(false);
  89. 	cin.tie(nullptr);
  90.  
  91. 	int t = 1;
  92. 	cin >> t;
  93.  
  94. 	for(int i = 1; i <= t; i++){
  95. 		solve();
  96. 	}
  97. 	return 0;
  98. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3
stdout
copy 
2
2
5
5
5
https://ideone.com/NN5aah
language:
C++14 (gcc 8.3)
created:
5 days 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!