fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. const int N = 1e5 + 5; 
  17.  
  18. int n, m;  
  19. vector<int> adj[N]; 
  20.  
  21. bool vis[N]; 
  22. vector<int> topo; 
  23.  
  24. void dfs(int u) {
  25. 	vis[u] = true;  
  26. 	for (int v : adj[u]) {
  27. 		if (!vis[v]) dfs(v); 
  28. 	}
  29. 	topo.push_back(u); 
  30. }
  31.  
  32. void topoSort() {
  33. 	for (int u = 1; u <= n; u++) {
  34. 		if (!vis[u]) dfs(u); 
  35. 	}
  36. 	reverse(topo.begin(), topo.end()); 
  37. }
  38.  
  39. int dp[N]; // dp[u] = Độ dài đường đi dài nhất kết thúc tại u
  40.  
  41. int main() {
  42. 	ios::sync_with_stdio(false); 
  43. 	cin.tie(nullptr); 	
  44. 	cin >> n >> m; 
  45.  
  46. 	for (int i = 0; i < m; i++) {
  47. 		int u, v; 
  48. 		cin >> u >> v; 
  49. 		adj[u].push_back(v); 
  50. 	}
  51.  
  52. 	topoSort();  
  53.  
  54. 	for (int u = 1; u <= n; u++) dp[u] = 0;   
  55.  
  56. 	for (int u : topo) {
  57. 		for (int v : adj[u]) {
  58. 			maximize(dp[v], dp[u] + 1);  
  59. 		}
  60. 	}
  61.  
  62. 	int ans = 0; 
  63. 	for (int u = 1; u <= n; u++) {
  64. 		maximize(ans, dp[u]);  
  65. 	}
  66.  
  67. 	cout << ans << '\n'; 
  68. }
Success #stdin #stdout 0.01s 5860KB
comments (?)
stdin
copy 
4 5
1 2
1 3
3 2
2 4
3 4
stdout
copy 
3
https://ideone.com/gbdX7h
language:
C++14 (gcc 8.3)
created:
289 days ago
visibility:
secret

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!