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:



Sample input:
4 5
1 2
1 3
3 2
2 4
3 4


Sample output:
3

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

N, M = input_nums()

G = {}
for i in range(N):
    G[i] = []

for i in range(M):
    x, y = input_nums()
    x -= 1
    y -= 1
    G[x].append(y)

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

def rec(v: int):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in G[v]:
        res = max(res, rec(nv) + 1)
    dp[v] = res
    return res

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

Submission status: Runtime Error

Solution code:
# Graph Problem DFS with DP(memoization)

n ,m = map(int, input().split())

dp = [-1] * n
arr = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    arr[a-1].append(b-1)

def dfs(ii):
    if dp[ii] != -1:
        return dp[ii]
    temp = 0
    # iterate through the connected vertices
    for aa in arr[ii]:
        temp = max(temp,dfs(aa) + 1)

    dp[ii] = temp
    return temp

ans = 0
# the max dist from the starting pos i
for i in range(n):

    ans = max(ans,dfs(i))
print(ans)

Submission status: Runtime Error

Solution code:
inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if g[x] == []:
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(1,N+1):
    g[i] = []

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)

Submission status: Runtime Error

Solution code:
def rec(x):
    if dp[x] != -1:
        return dp[x]

    else:
        g = 0
        for i in graph[x]:
            g = max(g, rec(i) + 1)
        dp[x] = g
        return dp[x]


n, m = map(int, input().split())

dp = [-1]*(n+1)
graph = [[] for _ in range(n)]
for i in range(m):
    x, y = tuple(map(int, input().split()))
    graph[x-1].append(y-1)

for i in range(n):
    rec(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
def rec(x):
    if dp[x] != 0:
        return dp[x]

    else:
        g = 0
        for i in graph[x]:
            g = max(g, rec(i) + 1)
        dp[x] = g
        return dp[x]


n, m = map(int, input().split())

dp = [0]*(n+1)
graph = [[] for _ in range(n)]
for i in range(m):
    x, y = tuple(map(int, input().split()))
    graph[x-1].append(y-1)

for i in range(n):
    rec(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2 << 30)

n, m = [int(i) for i in input().split()]
al = [set() for _ in range(n)]
for _ in range(m):
    x, y = [int(i) for i in input().split()]
    al[x-1].add(y-1)

dp = [-1] * n


def rec(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for nv in al[v]:
        ret = max(ret, rec(nv) + 1)
    dp[v] = ret
    return ret


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

print(ans)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
al = [set() for _ in range(n)]
for _ in range(m):
    x, y = [int(i) for i in input().split()]
    al[x-1].add(y-1)

dp = [-1] * n


def rec(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for nv in al[v]:
        ret = max(ret, rec(nv) + 1)
    dp[v] = ret
    return ret


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

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a].append(b)

dp = [-1] * N

def chdp(x):
    if dp[x] != -1:
        return(dp[x]) 
    dp[x] = 0
    for t in path[x]:
        dp[x] = max(dp[x], chdp(t)+1)
    return(dp[x])

for i in range(N):
    chdp(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------

def dfs(i):
    visited[i] = True
    for node in g[i]:
        if not visited[node]:
            dfs(node)
        dp[i] = max(dp[i], 1+ dp[node])



if __name__ == "__main__":
    n, m = rinput()
    g = defaultdict(list)
    for i in range(m):
        x, y = rinput()
        g[x].append(y)
    dp = [0]*(n+1)
    visited = [False]*(n+1)
    for i in range(1, n+1):
        if not visited[i]:
            dfs(i)
            # print('-=============================')
    # print(dp)
    print(max(dp))


# 5 3
# 2 3
# 2 4
# 5 2
# 5 1
# 1 4
# 4 3
# 1 3

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m=map(int,input().split())

visited = [False]*n
calculated = [False]*n
dp = [1]*MAXV # Vからスタートしたときの最長経路。頂点の個数ベースで経路の長さを数えるので、初期値は1

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1 # 計算が終わっていない頂点を2度訪れるのはループがあるということ
        return dp[v]
    visited[v] = True
    for u in to[v]: # 全ての辺をなめる
        res = dfs(u)
        if res == -1: return -1 # ループがあれば-1を返す
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

def main():
    to=[[] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        to[a].append(b)
    ans = 0
    for i in range(n):
        res = dfs(i)
        ans = max(ans, res)
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def rec(n):
  if dp[n] != -1:
    return dp[n]
  else:
    max_n = 0
    for i in graph[n]:
      max_n = max(max_n, rec(i)+1)
    dp[n] = max_n
    return dp[n]
  
N, M = list(map(int, input().split()))

dp = [-1]*n # nを始点としたときの最大値

graph = [[] for _ in range(N)]
for _ in range(M):
  xi, yi = list(map(int, input().split()))
  graph[xi-1].append(yi-1)

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

Submission status: Runtime Error

Solution code:
import numpy as np

def rec(n):
  if dp[n] != -1:
    return dp[n]
  else:
    max_n = 0
    for i in graph[n]:
      max_n = max(max_n, rec(i)+1)
    dp[n] = max_n
    return dp[n]
  
N, M = list(map(int, input().split()))

dp = np.full(N, -1, dtype=int) # nを始点としたときの最大値

graph = [[] for _ in range(N)]
for _ in range(M):
  xi, yi = list(map(int, input().split()))
  graph[xi-1].append(yi-1)

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(2*N)]
dp = [0 for n in range(2*N)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(2*N + 1)]
stack = []
def top_sort(node):
	visit[node] = True;
	for i in adj[node]:
		if visit[i] == False:
			top_sort(i);
		# top_sort(i)
	stack.append(node)
for a in range(N):
	if visit[a] == False:
		top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(2*N)]
dp = [0 for n in range(2*N)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	visit[node] = True;
	for i in adj[node]:
		if visit[i] == False:
			top_sort(i);
		# top_sort(i)
	stack.append(node)
for a in range(N):
	if visit[a] == False:
		top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	visit[node] = True;
	for i in adj[node]:
		if visit[i] == False:
			top_sort(i);
		# top_sort(i)
	stack.append(node)
for a in range(N):
	if visit[a] == False:
		top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	if visit[node] ==  False:
		for i in adj[node]:
			top_sort(i)
		stack.append(node)
		visit[node] = True
for a in range(N):
	if visit[a] == False:
		top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	visit[node] = True;
	for i in adj[node]:
		if visit[i] == False:
			top_sort(i)
	# stack.append(node)
for a in range(N):
	top_sort(a)
# stack.reverse()
# for p in stack:
# 	for q in adj[p]:
# 		dp[q] = max(dp[q], dp[p] + 1)
# # print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	visit[node] = True;
	for i in adj[node]:
		if visit[i] == False:
			top_sort(i)
	# stack.append(node)
for a in range(N):
	top_sort(a)
stack.reverse()
# for p in stack:
# 	for q in adj[p]:
# 		dp[q] = max(dp[q], dp[p] + 1)
# # print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	visit[node] = True;
	for i in adj[node]:
		if visit[i] == False:
			top_sort(i)
	stack.append(node)
for a in range(N):
	top_sort(a)
stack.reverse()
# for p in stack:
# 	for q in adj[p]:
# 		dp[q] = max(dp[q], dp[p] + 1)
# # print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N + 1)]
dp = [0 for n in range(N + 1)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N + 1)]
stack = []
def top_sort(node):
	if visit[node] ==  False:
		for i in adj[node]:
			top_sort(i)
		stack.append(node)
		visit[node] = True
for a in range(N):
	top_sort(a)
stack.reverse()
# for p in stack:
# 	for q in adj[p]:
# 		dp[q] = max(dp[q], dp[p] + 1)
# # print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	# dp[y-1] = 1
visit = [False for n in range(N)]
stack = []
def top_sort(node):
	if visit[node] ==  False:
		for i in adj[node]:
			top_sort(i)
		stack.append(node)
		visit[node] = True
for a in range(N):
	top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
g = [[] for i in range(n)]
 
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    g[x].append(y)
    
dp = [-1]*n
 
def dfs(i):
    #すでに計算されているなら
    if dp[i] != -1:
        return dp[i]
    #初期は長さ0
    tmp = 0
    #iからスタートしてつながっているところにDFS
    for j in g[i]:
        #今までの距離と比較
        tmp = max(tmp, dfs(j) + 1)
    #dp[i]はiからスタートして最長距離が記録される
    #空のリストにたどり着いたらDFS終わり
    dp[i] = tmp
    return tmp
 
for i in range(n):
    dfs(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
# Python3 program to find the  
# longest path in the DAG  
    
# Function to traverse the DAG  
# and apply Dynamic Programming  
# to find the longest path  
def dfs(node, adj, dp, vis):  
   
    # Mark as visited  
    vis[node] = True 
    
    # Traverse for all its children  
    for i in range(0, len(adj[node])):   
    
        # If not visited  
        if not vis[adj[node][i]]: 
            dfs(adj[node][i], adj, dp, vis)  
    
        # Store the max of the paths  
        dp[node] = max(dp[node], 1 + dp[adj[node][i]])  
    
# Function to add an edge  
def addEdge(adj, u, v):  
   
    adj[u].append(v)  
    
# Function that returns the longest path  
def findLongestPath(adj, n):  
   
    # Dp array  
    dp = [0] * (n + 1)  
      
    # Visited array to know if the node  
    # has been visited previously or not  
    vis = [False] * (n + 1) 
      
    # Call DFS for every unvisited vertex  
    for i in range(1, n + 1):   
        if not vis[i]:  
            dfs(i, adj, dp, vis)  
       
    ans = 0 
    
    # Traverse and find the maximum of all dp[i]  
    for i in range(1, n + 1):   
        ans = max(ans, dp[i])  
       
    return ans  
N, M = map(int, input().split())
# adj = [[] for i in range(N)]
# dp = [0 for n in range(N)]
adj = [[] for i in range(N + 1)] 
for m in range(M):
	x, y = map(int, input().split())
	addEdge(adj, x, y)
	# adj[x-1].append(y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N)]
# stack = []
# def top_sort(node):
# 	if visit[node] ==  False:
# 		for i in adj[node]:
# 			top_sort(i)
# 		stack.append(node)
# 		visit[node] = True
# for a in range(N):
# 	top_sort(a)
# stack.reverse()
# for p in stack:
# 	for q in adj[p]:
# 		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
# print(max(dp))
print(findLongestPath(adj, N))

Submission status: Runtime Error

Solution code:
#Python program to print topological sorting of a DAG 
from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) #dictionary containing adjacency List 
        self.V = vertices #No. of vertices 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    # A recursive function used by topologicalSort 
    def topologicalSortUtil(self,v,visited,stack): 
  
        # Mark the current node as visited. 
        visited[v] = True
  
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Push current vertex to stack which stores result 
        stack.insert(0,v) 
  
    # The function to do Topological Sort. It uses recursive  
    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 
  
        # Call the recursive helper function to store Topological 
        # Sort starting from all vertices one by one 
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Print contents of the stack 
        return stack 
N, M = map(int, input().split())
g = Graph(N)
# adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	# adj[x-1].append(y-1)
	g.addEdge(x-1, y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N)]
# stack = []
# def top_sort(node):
# 	# visit[node] = True
# 	for i in adj[node]:
# 		if visit[node] ==  False:
# 			top_sort(i)
# 	visit[node] = True
# 	stack.append(node)
# for a in range(N):
# 	if visit[a] ==  False:
# 		top_sort(a)
stack = g.topologicalSort()
# print(stack)
# stack.reverse()
for p in stack:
	if type(p) == int and p < N and p >= 0:
		for q in g.graph[p]:
			if type(q) == int and q < N and q >= 0:
				dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
ans = 0
for t in range(N):
	ans = max(ans, dp[t])
print(ans)

Submission status: Runtime Error

Solution code:
#Python program to print topological sorting of a DAG 
from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) #dictionary containing adjacency List 
        self.V = vertices #No. of vertices 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    # A recursive function used by topologicalSort 
    def topologicalSortUtil(self,v,visited,stack): 
  
        # Mark the current node as visited. 
        visited[v] = True
  
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Push current vertex to stack which stores result 
        stack.insert(0,v) 
  
    # The function to do Topological Sort. It uses recursive  
    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 
  
        # Call the recursive helper function to store Topological 
        # Sort starting from all vertices one by one 
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Print contents of the stack 
        return stack 
N, M = map(int, input().split())
g = Graph(N)
# adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	# adj[x-1].append(y-1)
	g.addEdge(x-1, y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N)]
# stack = []
# def top_sort(node):
# 	# visit[node] = True
# 	for i in adj[node]:
# 		if visit[node] ==  False:
# 			top_sort(i)
# 	visit[node] = True
# 	stack.append(node)
# for a in range(N):
# 	if visit[a] ==  False:
# 		top_sort(a)
stack = g.topologicalSort()
# print(stack)
# stack.reverse()
for p in stack:
	if type(p) == int and p < N and p >= 0:
		for q in g.graph[p]:
			if type(q) == int and q < N and q >= 0:
				dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
#Python program to print topological sorting of a DAG 
from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) #dictionary containing adjacency List 
        self.V = vertices #No. of vertices 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    # A recursive function used by topologicalSort 
    def topologicalSortUtil(self,v,visited,stack): 
  
        # Mark the current node as visited. 
        visited[v] = True
  
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Push current vertex to stack which stores result 
        stack.insert(0,v) 
  
    # The function to do Topological Sort. It uses recursive  
    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 
  
        # Call the recursive helper function to store Topological 
        # Sort starting from all vertices one by one 
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Print contents of the stack 
        return stack 
N, M = map(int, input().split())
g = Graph(N)
# adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	# adj[x-1].append(y-1)
	g.addEdge(x-1, y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N)]
# stack = []
# def top_sort(node):
# 	# visit[node] = True
# 	for i in adj[node]:
# 		if visit[node] ==  False:
# 			top_sort(i)
# 	visit[node] = True
# 	stack.append(node)
# for a in range(N):
# 	if visit[a] ==  False:
# 		top_sort(a)
stack = g.topologicalSort()
# print(stack)
# stack.reverse()
for p in stack:
	if type(p) == int and p < N:
		for q in g.graph[p]:
			if type(q) == int and q < N:
				dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
#Python program to print topological sorting of a DAG 
from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) #dictionary containing adjacency List 
        self.V = vertices #No. of vertices 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    # A recursive function used by topologicalSort 
    def topologicalSortUtil(self,v,visited,stack): 
  
        # Mark the current node as visited. 
        visited[v] = True
  
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Push current vertex to stack which stores result 
        stack.insert(0,v) 
  
    # The function to do Topological Sort. It uses recursive  
    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 
  
        # Call the recursive helper function to store Topological 
        # Sort starting from all vertices one by one 
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Print contents of the stack 
        return stack 
N, M = map(int, input().split())
g = Graph(N)
# adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	# adj[x-1].append(y-1)
	g.addEdge(x-1, y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N)]
# stack = []
# def top_sort(node):
# 	# visit[node] = True
# 	for i in adj[node]:
# 		if visit[node] ==  False:
# 			top_sort(i)
# 	visit[node] = True
# 	stack.append(node)
# for a in range(N):
# 	if visit[a] ==  False:
# 		top_sort(a)
stack = g.topologicalSort()
# print(stack)
# stack.reverse()
for p in stack:
	if type(p) == int:
		for q in g.graph[p]:
			if type(q) == int:
				dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
#Python program to print topological sorting of a DAG 
from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) #dictionary containing adjacency List 
        self.V = vertices #No. of vertices 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    # A recursive function used by topologicalSort 
    def topologicalSortUtil(self,v,visited,stack): 
  
        # Mark the current node as visited. 
        visited[v] = True
  
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Push current vertex to stack which stores result 
        stack.insert(0,v) 
  
    # The function to do Topological Sort. It uses recursive  
    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 
  
        # Call the recursive helper function to store Topological 
        # Sort starting from all vertices one by one 
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Print contents of the stack 
        return stack 
N, M = map(int, input().split())
g = Graph(N)
# adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	# adj[x-1].append(y-1)
	g.addEdge(x-1, y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N)]
# stack = []
# def top_sort(node):
# 	# visit[node] = True
# 	for i in adj[node]:
# 		if visit[node] ==  False:
# 			top_sort(i)
# 	visit[node] = True
# 	stack.append(node)
# for a in range(N):
# 	if visit[a] ==  False:
# 		top_sort(a)
stack = g.topologicalSort()
# print(stack)
# stack.reverse()
for p in stack:
	for q in g.graph[p]:
		if type(q) == int:
			dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
#Python program to print topological sorting of a DAG 
from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) #dictionary containing adjacency List 
        self.V = vertices #No. of vertices 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    # A recursive function used by topologicalSort 
    def topologicalSortUtil(self,v,visited,stack): 
  
        # Mark the current node as visited. 
        visited[v] = True
  
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Push current vertex to stack which stores result 
        stack.insert(0,v) 
  
    # The function to do Topological Sort. It uses recursive  
    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 
  
        # Call the recursive helper function to store Topological 
        # Sort starting from all vertices one by one 
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Print contents of the stack 
        return stack 
N, M = map(int, input().split())
g = Graph(N)
# adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	# adj[x-1].append(y-1)
	g.addEdge(x-1, y-1)
	# dp[y-1] = 1
# visit = [False for n in range(N)]
# stack = []
# def top_sort(node):
# 	# visit[node] = True
# 	for i in adj[node]:
# 		if visit[node] ==  False:
# 			top_sort(i)
# 	visit[node] = True
# 	stack.append(node)
# for a in range(N):
# 	if visit[a] ==  False:
# 		top_sort(a)
stack = g.topologicalSort()
# print(stack)
# stack.reverse()
for p in stack:
	for q in g.graph[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	# dp[y-1] = 1
visit = [False for n in range(N)]
stack = []
def top_sort(node):
	# visit[node] = True
	for i in adj[node]:
		if visit[node] ==  False:
			top_sort(i)
	visit[node] = True
	stack.append(node)
for a in range(N):
	if visit[a] ==  False:
		top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

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

"""
dp[v]: ノードv(1~N)を始点とした時の、最大長
"""
dp = [0] * (1+N)

def max_length_from(v):
    if dp[v] != 0:
        return dp[v]
    max_length = 0
    for vv in graph[v]:
        tmp = max_length_from(vv) + 1
        if tmp > max_length:
            max_length = tmp
    dp[v] = max_length
    return max_length

for v in range(1, N+1):
    max_length_from(v)

print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	# dp[y-1] = 1
visit = [False for n in range(N)]
stack = []
def top_sort(node):
	if visit[node] ==  False:
		for i in adj[node]:
			top_sort(i)
		stack.append(node)
		visit[node] = True
for a in range(N):
	top_sort(a)
rstack = []
for b in range(N-1, -1, -1):
	rstack.append(stack[b])
for p in rstack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for i in range(N)]
dp = [0 for n in range(N)]
for m in range(M):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	dp[y-1] = 1
visit = [False for n in range(N)]
stack = list()
def top_sort(node):
	if visit[node] ==  False:
		for i in adj[node]:
			top_sort(i)
		stack.append(node)
		visit[node] = True
for a in range(N):
	top_sort(a)
stack.reverse()
for p in stack:
	for q in adj[p]:
		dp[q] = max(dp[q], dp[p] + 1)
# print(dp)
print(max(dp))

Submission status: Runtime Error

Solution code:
n , m = map(int,input().split())
 
g = [[] for i in range(n)]
 
dp = [-1] *n
for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)
def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp = 0
  for nv in g[i]:
    temp = max(temp, dfs(nv)+1)
  dp[i]=temp
  return temp
res = 0  
for i in range(n):
  res = max(res, dfs(i))
  
print(res)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())

g = [[] for i in range(n)]

for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)

# longest path from vertice i
def dfs(i):
  temp = 0
  for nv in g[i]:
    temp = max(temp,dfs(nv)+1)
  return temp

# iterate over all vertices

res = 0
for i in range(n):
  res = max(res, dfs(i))
  
print(res)