[AtCoder] G - Longest Path

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : G - Longest Path
Source            : AtCoder Educational DP Contest
Category          : Dynamic Programing
Algorithm         : Dynamic Programing 
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 1e5 + 5;
 
int tnode, tedge;
vector <int> graph[maxn];
 
int dp[maxn];
bool memoize[maxn];
 
inline int longestPath(int u)
{
      int &ret = dp[u];
      bool &mem = memoize[u];
      if (mem) return ret;
      mem = 1;
      int maxi = 0;
      for (int v : graph[u])
      {
            int go = 1 + longestPath(v);
            if (go > maxi) maxi = go;
      }
      return ret = maxi;
}
 
int main()
{
      scanf("%d %d", &tnode, &tedge);
      for (int e = 1; e <= tedge; e++)
      {
            int u, v;
            scanf("%d %d", &u, &v);
            graph[u].emplace_back(v);
      }
      int maxi = 0;
      for (int i = 1; i <= tnode; i++)
      {
            if (longestPath(i) > maxi) maxi = longestPath(i);
      }
      printf("%d", maxi);
}
#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 1e5 + 5;
 
int tnode, tedge;
vector <int> graph[maxn];
 
int dp[maxn];
bool memoize[maxn];
 
inline int longestPath(int u)
{
      int &ret = dp[u];
      bool &mem = memoize[u];
      if (mem) return ret;
      mem = 1;
      int maxi = 0;
      for (int v : graph[u])
      {
            int go = 1 + longestPath(v);
            if (go > maxi) maxi = go;
      }
      return ret = maxi;
}
 
int main()
{
      scanf("%d %d", &tnode, &tedge);
      for (int e = 1; e <= tedge; e++)
      {
            int u, v;
            scanf("%d %d", &u, &v);
            graph[u].emplace_back(v);
      }
      int maxi = 0;
      for (int i = 1; i <= tnode; i++)
      {
            if (longestPath(i) > maxi) maxi = longestPath(i);
      }
      printf("%d", maxi);
}