Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class LongestPath
- {
- public static int memo[] = new int[100005];
- public static ArrayList<Integer>[] adj = new ArrayList[100005];
- public static int fun(int vertex)
- {
- if (adj[vertex].size() == 0)
- return 0;
- if (memo[vertex] != 0)
- return memo[vertex];
- for (Integer nextNode : adj[vertex])
- memo[vertex] = Math.max(memo[vertex], fun(nextNode) + 1);
- return memo[vertex];
- }
- public static void main(String[] args) throws IOException
- {
- for (int i = 0; i < 100005; i++)
- adj[i] = new ArrayList();
- BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
- String[] tmp = in.readLine().split(" ");
- int N = Integer.parseInt(tmp[0]);
- int M = Integer.parseInt(tmp[1]);
- for (int i = 0; i < M; i++)
- {
- tmp = in.readLine().split(" ");
- int x = Integer.parseInt(tmp[0]);
- int y = Integer.parseInt(tmp[1]);
- adj[x].add(y);
- }
- int ans = 0;
- for (int i = 1; i <= N; i++)
- ans = Math.max(ans, fun(i));
- System.out.println(ans);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement