Problem:
 Score : 100 points    Problem Statement There is a directed graph G with N vertices and M edges.
The vertices are numbered 1, 2, \ldots, N , and for each i ( 1 \leq i \leq M ), the i -th directed edge goes from Vertex x_i to y_i . G  does not contain directed cycles .  Find the length of the longest directed path in G .
Here, the length of a directed path is the number of edges in it.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq x_i, y_i \leq N  All pairs (x_i, y_i) are distinct.  G  does not contain directed cycles .         Input Input is given from Standard Input in the following format:  N  M  x_1  y_1  x_2  y_2  :  x_M  y_M       Output Print the length of the longest directed path in G .        Sample Input 1 4 5
1 2
1 3
3 2
2 4
3 4      Sample Output 1 3  The red directed path in the following figure is the longest:        Sample Input 2 6 3
2 3
4 5
5 6      Sample Output 2 2  The red directed path in the following figure is the longest:        Sample Input 3 5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3      Sample Output 3 3  The red directed path in the following figure is one of the longest:

Solution (Python):
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 100
import sys
sys.setrecursionlimit(1000000)

adj=[]
n,m = map(int,raw_input().split())
for i in range(n+1):
	adj.append([])
dp=[0]*(n+1)	
def dd(l):
	if(dp[l]!=-1):
		return dp[l]
	ma=dd(adj[l][0])
	for j in range(1,len(adj[l])):
		ma=max(ma,dd(adj[l][j]))
	dp[l]=ma+1
	return ma+1	
for i in range(m):
	x,y = map(int,raw_input().split())
	adj[y].append(x)
	dp[y]=-1
ans=[]
for i in range(1,n+1):
	ans.append(dd(i))
	
print max(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)


N, M = map(int, input().split())

G = {k: [] for k in range(N)}
for _ in range(M):
    x, y = map(int, input().split())

    
    G[x-1].append(y-1)  

dp = [-1 for _ in range(100100)]


def rec(v):
    if dp[v] != -1:
        return dp[v]

    dp[v] = 0
    for nv in G[v]:
        dp[v] = max(dp[v], rec(nv)+1)

    return dp[v]


ans = 0
for v in range(N):
    ans = max(ans, rec(v))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)


N, M = map(int, input().split())

G = {k: [] for k in range(N)}
for _ in range(M):
    x, y = map(int, input().split())

    
    G[x-1].append(y-1)  

dp = [-1 for _ in range(100100)]


def rec(v):
    if dp[v] != -1:
        return dp[v]

    dp[v] = 0
    for nv in G[v]:
        dp[v] = max(dp[v], rec(nv)+1)

    return dp[v]


ans = 0
for v in range(N):
    ans = max(ans, rec(v))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(524287)

n,m,*l = map(int,open(0).read().split())
pas = [[] for _ in range(n)]
for x,y in zip(l[::2],l[1::2]):
	pas[x-1].append(y-1)

INF = float("inf")
done = [-INF]*n

def dfs(t):
	if done[t] >= 0:
		pass
	elif pas[t]:
		done[t] = max(dfs(s) for s in pas[t]) + 1
	else:
		done[t] = 0
	return done[t]

print(max(dfs(i) for i in range(n)))

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(524287)

n,m,*l = map(int,open(0).read().split())
pas = [[] for _ in range(n)]
for x,y in zip(l[::2],l[1::2]):
	pas[x-1].append(y-1)

INF = float("inf")
done = [-INF]*n

@lru_cache(maxsize = None)
def dfs(t):
	if done[t] >= 0:
		pass
	elif pas[t]:
		done[t] = max(dfs(s) for s in pas[t]) + 1
	else:
		done[t] = 0
	return done[t]

print(max(dfs(i) for i in range(n)))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)

dp = [None] * (N+1)

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if graph[x]:
        dp[x] = 1 + max(dfs(y) for y in graph[x])
    else:
        dp[x] = 0
    return dp[x]

answer = max(dfs(x) for x in range(1,N+1))

print(answer)