title: Why doesn't this algorithm find the longest path in a directed acyclic graph?
body: <p>Ive tried to use dynamic programming to solve this question. dp[i] stores the the longest path ending at i. For every edge from x to y, i update dp[y] to the maximum between dp[y] and dp[x+1].</p>
  
  <p>It works on the input output examples but fails some of the testcases while being judged. Havent been able to think of a test case in which it fails.Any help would be appreciated.</p>
  
  <p><strong>N is number of vertices<br>
  M is number of edges<br>
  x y denotes an edge from x to y<br>
  Output should be the length of the longest path in the graph.</strong></p>
  
  <ul>
  <li>Sample Input<br>
  N M<br>
  x1 y1<br>
  x2 y2<br>
  x3 y3<br>
  .<br>
  .<br>
  .<br>
  Input 1<br>
  4 5<br>
  1 2<br>
  1 3<br>
  3 2<br>
  2 4<br>
  3 4<br>
  Output 1<br>
  3<br>
  Input 2<br>
  5 8<br>
  5 3<br>
  2 3<br>
  2 4<br>
  5 2<br>
  5 1<br>
  1 4<br>
  4 3<br>
  1 3<br>
  Output 2<br>
  3  </li>
  </ul>
  
  <pre><code>#include &lt;bits/stdc++.h&gt;
  using namespace std;
  
  
  int main()
  {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
  
      int n,m;
      cin&gt;&gt;n&gt;&gt;m;
  
      vector&lt;int&gt; dp(n+1,0);
      //dp[i] denotes max length of path ending at node i
      int x,y;
      for(int i=0;i&lt;m;i++)
      {
          cin&gt;&gt;x&gt;&gt;y;
          dp[y]=max(dp[x]+1,dp[y]);
      }
      int ans=0;
      // for(int i=0;i&lt;n+1;i++)
      //  cout&lt;&lt;i&lt;&lt; " : "&lt;&lt;dp[i]&lt;&lt;endl;
      for(int i=0;i&lt;n+1;i++)
          ans=max(ans,dp[i]);
      cout&lt;&lt;ans&lt;&lt;endl;
  }
  </code></pre>