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:
def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = 1
    p = 0
    for y in glaph[x]:
        p = max(p,f(y)+1)
    dp[x] = p
    return dp[x]
n,m = map(int,input().split())
glaph = [[] for i in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    glaph[x].append(y)
flag = [0]*(n+1)
dp = [0]*(n+1)
for i in range(1,n+1):
    f(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = 1
    p = 0
    for y in glaph[x]:
        p = max(p,f(y)+1)
    dp[x] = p
    return dp[x]
n,m = map(int,input().split())
glaph = [[] for i in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    glaph[x].append(y)
flag = [0]*(n+1)
dp = [0]*(n+1)
ans = 0
for i in range(1,n+1):
    ans = max(ans,f(i))
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    if len(glaph[x]) == 0:
        return dp[x]
    y = 0
    for i in glaph[x]:
        y = max(y,f(i)+1)
    dp[x] = y
    return dp[x]
n,m = map(int,input().split())
glaph = [[] for i in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    glaph[x].append(y)
dp = [0]*(n+1)
ans = 0
for i in range(1,n+1):
    ans = max(ans,f(i))
print(ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfs(self, node):
        ans = 0
        for child in self.adj[node]:
            ans = max(ans, 1 + self.dfs(child))
        return ans

    def dfsWithMemo(self, node, memo, visited):
        if(visited[node]):
            return memo[node]
        visited[node] = True
        for child in self.adj[node]:
            memo[node] = max(
                memo[node], 1 + self.dfsWithMemo(child, memo, visited))
        return memo[node]

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    # o(n^2) solution
    def findLongestPathNaive(self):
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfs(i))
        return ans

    # o(n) solution
    def findLongestPathWithMemo(self):
        visited = [False] * self.n
        memo = [0] * self.n
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithMemo(i, memo, visited))
        return ans

    # O(n) solution
    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    # print(dag.findLongestPathNaive())
    #  print(dag.findLongestPathWithMemo())
     print(dag.findLongestPathWithDp())


main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
d=defaultdict(list)
for _ in range(m):
  x,y=map(int,input().split())
  d[x-1].append(y-1)

dp=[-1]*n

def rec(v):
  if dp[v]!=-1:
    return dp[v]
  res=0
  for nv in d[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:
def li():
    return [int(x) for x in input().split()]

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

INF = 10 ** 60

G = defaultdict(list)

N, M = li()

for _ in range(M):
    x, y = li()
    G[x].append(y)

dp = [-1] * (10 ** 5)

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for cv in G[v]:
        ret = max(ret, dfs(cv) + 1)
    dp[v] = ret
    return ret


ans = 0
for v in range(1, N+1):
    # print(dfs(v))
    ans = max(ans, dfs(v))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

G = defaultdict(list)

N, M = li()

for _ in range(M):
    x, y = li()
    G[x].append(y)

dp = [-1] * (10 ** 5)

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for cv in G[v]:
        ret = max(ret, dfs(cv) + 1)
    dp[v] = ret
    return ret


ans = 0
for v in range(1, N+1):
    # print(dfs(v))
    ans = max(ans, dfs(v))

print(ans)

Submission status: Runtime Error

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

dp = [-1]*N
def rec(v):
  if dp[v] != -1:
    return dp[v]
  
  res = 0
  for nv in graph[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:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  graph[x].append(y)

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

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

Submission status: Runtime Error

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

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

for _ in range(m):
    x, y = map(int, input().split())
    V[x-1].append(y-1)

def f(x):
    if dp[x] != -1:
        return dp[x]

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return t

t = 0
for i in range(n):
    t = max(t, f(i))

print(t)

Submission status: Runtime Error

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

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

for _ in range(m):
    x, y = map(int, input().split())
    V[x-1].append(y-1)

def f(x):
    if dp[x] != -1:
        return dp[x]

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return t

t = 0
for i in range(n):
    t = max(t, f(i))

print(t)

Submission status: Runtime Error

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

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return t

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

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

for _ in range(m):
    x, y = map(int, input().split())
    V[x-1].append(y-1)

t = 0
for i in range(n):
    t = max(t, f(i))

print(t)

Submission status: Runtime Error

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

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return t

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

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

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

t = 0
for i in range(1, n+1):
    t = max(t, f(i))

print(t)

Submission status: Runtime Error

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

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

for i in range(m):
    x, y = map(int, input().split())
    V[x].append(y)

def f(x):
    if dp[x] != -1:
        return dp[x]

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return dp[x]


t = 0
for i in range(1, n+1):
    t = max(t, f(i))

print(t)

Submission status: Runtime Error

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

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return dp[x]

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

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

for i in range(m):
    x, y = map(int, input().split())
    V[x].append(y)

t = 0
for i in range(1, n+1):
    t = max(t, f(i))

print(t)

Submission status: Runtime Error

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

    t = 0
    for v in V[x][1]:
        t = max(t, f(v)+1)

    dp[x] = t
    return dp[x]

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

dp = [-1]*(n+1)
V = [[i, []] for i in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())
    V[x][1].append(y)

t = 0
for i in range(1, n+1):
    t = max(t, f(i))
print(t)

Submission status: Runtime Error

Solution code:
# import sys
from collections import defaultdict
# sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
d = defaultdict(list)
for i in range(m):
    x,y = map(int,input().split())
    d[x-1].append(y-1)

dp = [-1]*n

def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in d[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:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

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

N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)

flag = [False] * (N + 1)
dp = [0] * (N + 1)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return dp[x]

ans = 0
for i in range(1, N + 1):
    ans = max(ans, f(i))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

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

N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)

flag = [False] * (N + 1)
dp = [0] * (N + 1)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return fans

ans = 0
for i in range(1, N + 1):
    ans = max(ans, f(i))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

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

N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)
_debug(graph)

flag = [False] * (N + 1)
_debug(flag)
dp = [0] * (N + 1)
_debug(dp)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return fans

ans = 0
for i in range(1, N + 1):
    ans = max(ans, f(i))
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    edges[y-1].append(x-1)
    
used = [0 for _ in range(N)]
dp = [0 for _ in range(N)]

def dfs(pos):
    if not edges[pos]:
        dp[pos] = 0
        return
    for n_pos in edges[pos]:
        if not used[n_pos]:
            dfs(n_pos)
        used[n_pos] = 1
        dp[pos] = max(dp[pos],dp[n_pos]+1)
    print(dp)
    
for i in range(N):
    if used[i]:
        continue
    used[i] = True
    dfs(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ad = [[] for i in range(N+1)]
for i in range(M):
  x, y = map(int, input().split())
  ad[x].append(y)
def f(x, p):
  ret = 0
  for i in ad[x]:
    ret = max(ret, f(i, x) + 1)
  return ret
ans = 0
for i in range(1, N+1):
  ans = max(ans, f(i, -1))
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())

G=[[] for i in range(N)] #グラフを隣接リストで表現
for j in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)

dp=[-1]*N

def longest_path(v): #vを始点とした時の最長パスの長さ
    if dp[v] != -1: #更新済みの場合
        return dp[v]
    
    #更新されていなかった場合
    tmp_max = 0
    for u in G[v]:
        tmp_max = max(tmp_max,longest_path(u)+1)
    dp[v] = tmp_max #きちんとメモする
    
    return dp[v]

ans=0
for i in range(N):
    ans = max(ans,longest_path(i))

print(ans)

Submission status: Runtime Error

Solution code:
def read_pair():
    return map(int, input().strip().split())

# Read graph
N, M = read_pair()
adj = [[] for x in range(N)]
for i in range(M):
    x, y = read_pair()
    adj[x - 1].append(y - 1)

memo = [None] * N

def longest_path(x, memo):
    if memo[x] is not None:
        return memo[x]

    result = 0
    for y in adj[x]:
        result = max(result, 1 + longest_path(y, memo))
    memo[x] = result
    return result

result = 0
for x in range(N):
    result = max(result, longest_path(x, memo))
print(result)

Submission status: Runtime Error

Solution code:
def read_pair():
    return map(int, input().strip().split())

# Read graph
N, M = read_pair()
adj = [[] for x in range(N + 1)]
for i in range(M):
    x, y = read_pair()
    adj[x].append(y)

memo = [None] * (N + 1)

def longest_path(x, memo):
    if memo[x] is not None:
        return memo[x]

    result = 0
    for y in adj[x]:
        result = max(result, 1 + longest_path(y, memo))
    memo[x] = result
    return result

result = 0
for x in range(1, N + 1):
    result = max(result, longest_path(x, memo))
print(result)

Submission status: Runtime Error

Solution code:
def read_pair():
    return map(int, input().split())

# Read graph
N, M = read_pair()
adj = [[] for i in range(N + 1)]
for i in range(M):
    x, y = read_pair()
    adj[x].append(y)

memo = [None] * (N + 1)

def longest_path(x, memo):
    if memo[x] is not None:
        return memo[x]

    result = 0
    for y in adj[x]:
        result = max(result, 1 + longest_path(y, memo))
    memo[x] = result
    return result

result = 0
for x in range(1, N + 1):
    result = max(result, longest_path(x, memo))
print(result)

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        graph[x].append(y)
    dp = [-1 for _ in range(n)]
    # dp[i] := iから距離が最も長い頂点への距離

    def solve(v):
        if dp[v] != -1:
            return dp[v]
        res = 0
        for next_v in graph[v]:
            res = max(res, solve(next_v) + 1)
        dp[v] = res
        return dp[v]

    ans = 0
    for i in range(n):
        ans = max(ans, solve(i))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def f(i, e, dp):
    if dp[i] is not None:
        return dp[i]
    val = 0
    for nxt in e[i]:
        val = max(val, f(nxt, e, dp) + 1)
    dp[i] = val
    return dp[i]


def edu_dp_g_longest_path():
    n, m = map(int, input().split())
    e = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        e[x - 1].append(y - 1)
    dp = [None] * n
    result = 0
    for i in range(n):
        result = max(result, f(i, e, dp))
    print(result)

edu_dp_g_longest_path()

Submission status: Runtime Error

Solution code:
def f(i, e, dp):
    if dp[i] is not None:
        return dp[i]
    val = 0
    for nxt in e[i]:
        val = max(val, f(nxt, e, dp) + 1)
    dp[i] = val
    return val


def edu_dp_g_longest_path():
    n, m = map(int, input().split())
    e = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        e[x - 1].append(y - 1)
    dp = [None] * n
    result = [f(i, e, dp) for i in range(n)]
    print(max([0]+[r for r in result if r is not None]))
edu_dp_g_longest_path()

Submission status: Runtime Error

Solution code:
def f(i, e, dp):
    if dp[i] is not None:
        return dp[i]
    val = 0
    for nxt in e[i]:
        val = max(val, f(nxt, e, dp) + 1)
    dp[i] = val
    return val


def edu_dp_g_longest_path():
    n, m = map(int, input().split())
    e = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        e[x - 1].append(y - 1)
    dp = [None] * n

    print(max([f(i, e, dp) for i in range(n)]))
edu_dp_g_longest_path()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

graph = [[] for _ in range(110000)]

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

    graph[x].append(y)

dp_memo = [-1] * 110000

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

    ret = 0
    for item in graph[v]:
        ret = max(ret, dp(item) + 1)

    dp_memo[v] = ret
    return ret

ans = 0

for i in range(1, N+1):
    ans = max(ans, dp(i))

print(ans)

Submission status: Runtime Error

Solution code:
import collections
def dfs(v,visited,dp,adj):
	visited[v]=True 
	for i in adj[v]:
		if not visited[i]: 
			dfs(i,visited,dp,adj) 
		dp[v]=max(dp[v],1+dp[i])  

adj=collections.defaultdict(list)
n,m=map(int,input().split()) 
for i in range(m):
	u,v=map(int,input().split()) 
	adj[u].append(v)
visited=[False]*(n+1)
dp=[0]*(n+1) 
for i in range(1,n+1):
	if not visited[i]:
		dfs(i,visited,dp,adj) 
print(max(dp))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst_edge=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  # 最初のindexをゼロにする
  lst_edge[x-1].append(y-1)
#print(lst_edge)
# dp[v] := ノードvを始点とした時の有向パスの長さの最大値
# -1 未訪問で初期化。
dp=[-1]*n
 
def rec(v):
  #更新済み
  if dp[v]!=-1:
    return dp[v]
  ans=0
  lst_nv=lst_edge[v]
  for nv in lst_nv:
    ans=max(ans,rec(nv)+1)
  dp[v]=ans
  #print(dp)
  return dp[v]
  
ans=0
for i in range(n):
  ans=max(ans,rec(i))
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst_edge=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  # 最初のindexをゼロにする
  lst_edge[x-1].append(y-1)
#print(lst_edge)
# dp[v] := ノードvを始点とした時の有向パスの長さの最大値
# -1 未訪問で初期化。
dp=[-1]*n

def rec(v):
  #更新済み
  if dp[v]!=-1:
    return dp[v]
  ans=0
  lst_nv=lst_edge[v]
  for nv in lst_nv:
    ans=max(ans,rec(nv)+1)
  dp[v]=ans
  #print(dp)
  return dp[v]
  
ans=0
for i in range(n):
  ans=max(ans,rec(i))
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())  #vertices,edges
adj=[[] for _ in range(n)]
visited=[False for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    adj[x-1].append(y-1)
dp=[0 for _ in range(n)]

def dfs(node,adj,visited,dp):
    visited[node]=True
    
    for i in adj[node]:
        if not visited[i]:
            dfs(i,adj,visited,dp)
        dp[node]=max(dp[node],dp[i]+1)
if m==1:
    print(1)
else:
    for j in range(n):
        if visited[j]==False:
            # print(j)
            dfs(j,adj,visited,dp)
            # print(visited)

# print(dp)
    print(max(dp))
# print(adj)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())  #vertices,edges
adj=[[] for _ in range(n)]
visited=[False for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    adj[x-1].append(y-1)
dp=[0 for _ in range(n)]

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

for j in range(n):
    if visited[j]==False:
        # print(j)
        dfs(j,adj,visited,dp)
        # print(visited)

# print(dp)
print(max(dp))
# print(adj)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())  #vertices,edges
adj=[[] for _ in range(n)]
visited=[False for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    adj[x-1].append(y-1)
dp=[0 for _ in range(n)]

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

for j in range(n):
    if not visited[j]:
        dfs(j)
print(max(dp))

Submission status: Runtime Error

Solution code:
N,M=list(map(int, input().split()))
P=[set() for _ in range(N)]
for i in range(M):
    x,y=list(map(int, input().split()))
    x-=1
    y-=1
    P[x].add(y)

dp=[-1]*N

def lpth(n):
    if dp[n]>-1:
        return dp[n]
    l=P[n]
    # print(l)
    if l:
        s=[lpth(k) for k in l]
        # print(s)
        a=max(s)+1
    else:
        a=0
    dp[n]=a
    return a

for i in range(N):
    dp[i]=lpth(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())  #vertices,edges
adj=[[] for _ in range(n)]
visited=[False for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    adj[x-1].append(y-1)
dp=[0 for _ in range(n)]

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

for j in range(n):
    if not visited[j]:
        dfs(j)
print(max(dp))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())  #vertices,edges
adj=[[] for _ in range(n)]
visited=[False for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    adj[x-1].append(y-1)
dp=[0 for _ in range(n)]

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

for j in range(n):
    if not visited[j]:
        dfs(j)
print(max(dp))

Submission status: Runtime Error

Solution code:
import heapq
INF=float('inf')

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

def f(k):
  if dp[k]!=-1:
    return dp[k]
  
  dp[k]=0
  if adj[k]:
    for v in adj[k]:
      dp[k]=max(dp[k],f(v)+1)
  return dp[k]

dp[0]=0
for i in range(1,n+1):
  dp[i]=-1

ans=-INF  
for i in range(1,n+1):
  ans=max(ans,f(i))

print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(M):
  a,b=map(int,input().split())
  G[b-1].append(a-1)
DP=[-1]*N
def f(x):
  if DP[x]!=-1:
    return DP[x]
  DP[x]=0
  for i in range(len(G[x])):
    DP[x]=max(DP[x],f(G[x][i])+1)
  return DP[x]

for i in range(N):
  f(i)
print(max(DP))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def longest_path(s):
    global dp
    if dp[s-1]<1:
        if edge[s]:
            dp[s-1]=max((longest_path(t)+1)for t in edge[s])
        else:
            dp[s-1]=0
    return dp[s-1]

N,M=map(int,input().split())
edge={}
for i in range(1,N+1):
    edge.setdefault(i,[])
for _ in range(M):
    x,y=map(int,input().split())
    edge[x].append(y)
dp=[0]*N
for i in range(1,N+1):
    if dp[i-1]==0:
        longest_path(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def longest_path(s):
    global dp
    if dp[s-1]>=1:
        return dp[s-1]
    else:
        if edge[s]:
            dp[s-1]=max((longest_path(t)+1)for t in edge[s])
        else:
            dp[s-1]=0
    return dp[s-1]

N,M=map(int,input().split())
edge={}
for i in range(1,N+1):
    edge.setdefault(i,[])
for _ in range(M):
    x,y=map(int,input().split())
    edge[x].append(y)
dp=[0]*N
check=[False]*N
for i in range(1,N+1):
    if dp[i-1]==0:
        longest_path(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    G[x].append(y)

dp = [-1]*(n+1)
# dp[i]:頂点iに到達したときの有向辺の最長の長さ
def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    res = 0
    for nx in G[cur]:
        res = max(res,dfs(nx)+1)
    dp[cur] = res
    return res
    
for i in range(n):
    dp[i] = max(dp[i],dfs(i))

print(max(dp))

Submission status: Runtime Error

Solution code:


def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
#%%
for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)

#%%
ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.getrecursionlimit(10 ** 9)

def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
#%%
for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)

#%%
ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.getrecursionlimit(1e9)

def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
#%%
for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)

#%%
ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)

Submission status: Runtime Error

Solution code:

def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
#%%
for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)

#%%
ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)