Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class LongestPath
  5. {
  6. public static int memo[] = new int[100005];
  7. public static ArrayList<Integer>[] adj = new ArrayList[100005];
  8.  
  9. public static int fun(int vertex)
  10. {
  11. if (adj[vertex].size() == 0)
  12. return 0;
  13. if (memo[vertex] != 0)
  14. return memo[vertex];
  15. for (Integer nextNode : adj[vertex])
  16. memo[vertex] = Math.max(memo[vertex], fun(nextNode) + 1);
  17. return memo[vertex];
  18. }
  19.  
  20. public static void main(String[] args) throws IOException
  21. {
  22. for (int i = 0; i < 100005; i++)
  23. adj[i] = new ArrayList();
  24. BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  25. String[] tmp = in.readLine().split(" ");
  26. int N = Integer.parseInt(tmp[0]);
  27. int M = Integer.parseInt(tmp[1]);
  28. for (int i = 0; i < M; i++)
  29. {
  30. tmp = in.readLine().split(" ");
  31. int x = Integer.parseInt(tmp[0]);
  32. int y = Integer.parseInt(tmp[1]);
  33. adj[x].add(y);
  34. }
  35. int ans = 0;
  36. for (int i = 1; i <= N; i++)
  37. ans = Math.max(ans, fun(i));
  38. System.out.println(ans);
  39. }
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement