Advertisement
Josif_tepe

Untitled

Nov 15th, 2021
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include <iostream>
  2. #include<ctime>
  3. #include<map>
  4. #include<vector>
  5. #include<queue>
  6. using namespace std;
  7. int n;
  8. int m;
  9. vector<int>graph[100005];
  10. int dp[100005];
  11. int rec(int i=0){
  12.  
  13. if(dp[i]!=-1){
  14.     return(dp[i]);
  15. }
  16.  
  17. int result=0;
  18.  
  19. for(int j=0; j<graph[i].size(); j++){
  20. result=max(result, rec(graph[i][j])+1);
  21. }
  22.     dp[i] = result;
  23. return(result);
  24. }
  25. int main()
  26. {
  27. cin>>n;
  28. cin>>m;
  29.  
  30. for(int i=0; i<m; i++){
  31. int a;
  32. int b;
  33. cin>>a>>b;
  34. graph[a].push_back(b);
  35. }
  36.  
  37. for(int i=0; i<=n; i++){
  38.     dp[i]=-1;
  39. }
  40. int result1=0;
  41. for(int i=0; i<=n; i++){
  42.     result1=max(result1, rec(i));
  43. }
  44. cout<<result1;
  45.     return 0;
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement