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 rec(v):
    if dp[v] != -1: return dp[v]
    res = 0
    for nv in es[v]:
        res = max(res, rec(nv) + 1)
    dp[v] = res
    return res


N, M = map(int, input().split())
es = [[] for _ in range(N)]

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

dp = [-1] * N

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())
        
G = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    
dp = [-1] * (N)

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
def sub():

    N, M = [int(e) for e in input().split()]
    es = [[int(x) for x in input().split()] for _ in range(N)]

    outs = defaultdict(list)
    ins = defaultdict(int)
    for v1, v2 in es:
        outs[v1].append(v2)
        ins[v2] += 1

    q = deque(v1 for v1 in range(1, N+1) if ins[v1] == 0)
    dp_table = [0 for i in range(N+1)]
    res = []
    while q:
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)
                dp_table[v2] = max(dp_table[v2], dp_table[v1] + 1)
    print(max(dp_table))

if __name__ == "__main__":
    sub()

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
def sub():

    N, M = [int(e) for e in input().split()]
    es = [[int(x) for x in input().split()] for _ in range(N)]

    outs = defaultdict(list)
    ins = defaultdict(int)
    for v1, v2 in es:
        outs[v1].append(v2)
        ins[v2] += 1

    q = deque(v1 for v1 in range(v) if ins[v1] == 0)
    dp_table = [0 for i in range(N+1)]
    res = []
    while q:
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)
                dp_table[v2] = max(dp_table[v2], dp_table[v1] + 1)
    print(max(dp_table))

if __name__ == "__main__":
    sub()

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def sub():
    N, M = [int(e) for e in input().split()]
    
    class ListDict(dict):
        def __missing__(self, key):
            self[key] = []
            return self[key]

    d_edge = ListDict()
    for _ in range(M):
        h, t = [int(e) for e in input().split()]
        d_edge[h].append(t)

    # for k, v in d_edge.items():
    #     print(k,v)
    
    mem_dp_value = {}
    def dp(a_head):
        if a_head in mem_dp_value:
            return mem_dp_value[a_head]

        tails = d_edge[a_head]
        if len(tails) == 0:
            return 0
        tmps = [dp(t) for t in tails]
        ans = max(tmps) + 1
        mem_dp_value[a_head] = ans
        return ans
    
    heads = list(d_edge.keys())
    rr = [dp(h) for h in heads]
    print(max(rr))


if __name__ == "__main__":
    sub()

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def sub():
    N, M = [int(e) for e in input().split()]
    
    class ListDict(dict):
        def __missing__(self, key):
            self[key] = []
            return self[key]

    d_edge = ListDict()
    for _ in range(M):
        h, t = [int(e) for e in input().split()]
        d_edge[h].append(t)

    # for k, v in d_edge.items():
    #     print(k,v)
    
    @lru_cache(maxsize=None)
    def dp(a_head):
        tails = d_edge[a_head]
        if len(tails) == 0:
            return 0
        tmps = [dp(t) for t in tails]
        return max(tmps) + 1
    
    heads = list(d_edge.keys())
    rr = [dp(h) for h in heads]
    print(max(rr))


if __name__ == "__main__":
    sub()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def MI(): return map(int, input().split())


def LI(): return list(mi())


def LI_(): return [int(x) - 1 for x in input().split()]


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [li() for _ in range(n)]


def LLIN_(n: int): return [li_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y = LI_()
        edge[x].append(y)

    def go_to_leaf(n):
        if dp[n] >= 0:
            return dp[n]
        ret = 0
        for y in edge[n]:
            ret = max(go_to_leaf(y) + 1, ret)
        dp[n] = ret
        return ret

    dp = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, go_to_leaf(i))
    print(ans)

    """start = 0
    while rev_edge[start]:
        start = rev_edge[start][0]
    stack = set([start])
    ans = 0
    for _ in range(N + 1):
        tmp = []
        print(stack)
        while stack:
            now = stack.pop()
            tmp.extend(edge[now])
        if not tmp:
            print(tmp)
            break
        stack = set(tmp)
        ans += 1
    print(ans)"""


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def get_nagasa(i):
    if nagasa[i] != -1:
        return nagasa[i]
    if ko[i] == []:
        nagasa[i] = 0
        return 0
    re = 0
    for ii in ko[i]:
        p = get_nagasa(ii) + 1
        if p > re:
            re = p
    nagasa[i] = re
    return re

n, m = map(int, input().split())
ko = [[] for _ in range(n)]
nagasa = [-1] * n
for _ in range(m):
    x, y = map(int, input().split())
    ko[x - 1] += [y - 1]
mx = 0
for i in range(n):
    tmp = get_nagasa(i)
    if tmp > mx:
        mx = tmp
print(mx)

Submission status: Runtime Error

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

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

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

dp = [-1] * N
length = [0] * N

def count(j):
    if dp[j] != -1:
        return(dp[j])
    else:
        dp[j] = 0
        for k in graph[j]:
            dp[j] = max(count(k)+1, dp[j])
        return dp[j]

for i in range(N):
    length[i] = count(i)

print(max(length))

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
from functools import reduce

n,m = map(int,input().split())
dp = [-1]*100100
#初期化
G = defaultdict(set)
for i in range(m):
    x,y = map(int,input().split())
    G[x-1].add(y-1)
for v in range(n):
    dp[v] = -1
#vからスタートしたロンゲストパスの長さを計算する関数
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for u in G[v]:
        res = max(res,rec(u)+1)
    dp[v] = res
    return res

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

Submission status: Runtime Error

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

dp = [-1] * n
def count(a):
    if dp[a] != -1:
        return dp[a]
    else:
        dp[a] = 0
        for i in graph[a]:
            dp[a] = max(count(i) + 1, dp[a])
        return dp[a]

print(max([count(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x - 1].append(y - 1)

dp = [-1] * n
def count(a):
    if dp[a] != -1:
        return dp[a]
    else:
        dp[a] = 0
        for i in graph[a]:
            dp[a] = max(count(i) + 1, dp[a])
        return dp[a]

print(max([count(i) for i in range(n)]))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

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

g = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().rstrip().split(' '))
    g[y-1].append(x-1)
    
dp = [-1] * N
def rec(v):
    if dp[v] != -1:
        return dp[v]
        
    count = 0
    for x in g[v]:
        count = max(count, rec(x)+1)
        
    dp[v] = count
    
    return count
   
for i in range(N):
    rec(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.insert(0, i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    xv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for x, v in xv:
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = []

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = tsort_res[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print(max(dp))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    #raw = ["4 5",
    #       "1 2",
    #       "1 3",
    #       "3 2",
    #       "2 4",
    #       "3 4"]
    #raw = ["5 8",
    #       "5 3",
    #       "2 3",
    #       "2 4",
    #       "5 2",
    #       "5 1",
    #       "1 4",
    #       "4 3",
    #       "1 3"]
    #N, M = map(int, raw[0].split())
    #graph = [[] for _ in range(N+1)]
    #for i in range(1, M+1):
    #    s, t = map(int, raw[i].split())
    #    graph[s].append(t)
    import sys
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for i in range(1, M+1):
        s, t = map(int, sys.stdin.readline().split())
        graph[s].append(t)
    memo = [0] * (N + 2)
    used = [False] * (N + 2)
    def dfs(u):
        if len(graph[u]) == 0:
            return 0
        if used[u]:
            return memo[u]
        for v in graph[u]:
            memo[u] = max(memo[u], 1 + dfs(v))
        used[u] = True
        return memo[u]
    ans = 0
    for i in range(1, N+1):
        ans = max(dfs(i), ans)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    #raw = ["4 5",
    #       "1 2",
    #       "1 3",
    #       "3 2",
    #       "2 4",
    #       "3 4"]
    #raw = ["5 8",
    #       "5 3",
    #       "2 3",
    #       "2 4",
    #       "5 2",
    #       "5 1",
    #       "1 4",
    #       "4 3",
    #       "1 3"]
    #N, M = map(int, raw[0].split())
    #graph = [[] for _ in range(N+1)]
    #for i in range(1, M+1):
    #    s, t = map(int, raw[i].split())
    #    graph[s].append(t)
    import sys
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for i in range(1, M+1):
        s, t = map(int, sys.stdin.readline().split())
        graph[s].append(t)
    memo = [0] * (N + 2)
    used = [False] * (N + 2)
    def dfs(u):
        if len(graph[u]) == 0:
            return 0
        if used[u]:
            return memo[u]
        for v in graph[u]:
            memo[u] = max(memo[u], 1 + dfs(v))
        used[u] = True
        return memo[u]
    ans = 0
    for i in range(1, N+2):
        ans = max(dfs(i), ans)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    #raw = ["4 5",
    #       "1 2",
    #       "1 3",
    #       "3 2",
    #       "2 4",
    #       "3 4"]
    #raw = ["5 8",
    #       "5 3",
    #       "2 3",
    #       "2 4",
    #       "5 2",
    #       "5 1",
    #       "1 4",
    #       "4 3",
    #       "1 3"]
    #N, M = map(int, raw[0].split())
    #graph = [[] for _ in range(N+1)]
    #for i in range(1, M+1):
    #    s, t = map(int, raw[i].split())
    #    graph[s].append(t)
    import sys
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for i in range(1, M+1):
        s, t = map(int, sys.stdin.readline().split())
        graph[s].append(t)
    memo = [0] * (N + 1)
    used = [False] * (N + 1)
    def dfs(u):
        if len(graph[u]) == 0:
            return 0
        if used[u]:
            return memo[u]
        for v in graph[u]:
            memo[u] = max(memo[u], 1 + dfs(v))
        used[u] = True
        return memo[u]
    ans = 0
    for i in range(1, N+1):
        ans = max(dfs(i), ans)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    #raw = ["4 5",
    #       "1 2",
    #       "1 3",
    #       "3 2",
    #       "2 4",
    #       "3 4"]
    #N, M = map(int, raw[0].split())
    #graph = [[] for _ in range(N+1)]
    #for i in range(1, M+1):
    #    s, t = map(int, raw[i].split())
    #    graph[s].append(t)
    #print(graph)
    import sys
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for i in range(1, M+1):
        s, t = map(int, sys.stdin.readline().split())
        graph[s].append(t)

    memo = [0] * N
    used = [False] * N
    def dfs(u):
        if len(graph[u]) == 0:
            return 0
        if used[u]:
            return memo[u]
        for v in graph[u]:
            memo[u] = max(memo[u], 1 + dfs(v))
        used[u] = True
        return memo[u]
    ans = 0
    for i in range(1, N+1):
        ans = max(dfs(i), ans)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    #raw = ["4 5",
    #       "1 2",
    #       "1 3",
    #       "3 2",
    #       "2 4",
    #       "3 4"]
    #N, M = map(int, raw[0].split())
    #graph = [[] for _ in range(N+1)]
    #for i in range(1, M+1):
    #    s, t = map(int, raw[i].split())
    #    graph[s].append(t)
    #print(graph)
    import sys
    N, M = map(int, sys.stdin.readline().split())
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
    for i in range(1, M+1):
        s, t = map(int, sys.stdin.readline().split())
        graph[s].append(t)

    memo = [0] * N
    used = [False] * N
    def dfs(u):
        if len(graph[u]) == 0:
            return 0
        if used[u]:
            return memo[u]
        for v in graph[u]:
            memo[u] = max(memo[u], 1 + dfs(v))
        used[u] = True
        return memo[u]
    ans = 0
    for i in range(1, N+1):
        ans = max(dfs(i), ans)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)


N, M = map(int, input().split())
XY = [map(int, input().split()) for _ in range(M)]

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

x_to_y = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)


@lru_cache(N)
def depth(n):
    ret = -1
    for y in x_to_y[n]:
        ret = max(ret, depth(y))
    return ret + 1


        
depths = [depth(n) for n in range(1, N + 1)]
print(max(depths), default=0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from functools import lru_cache

N, M = map(int, input().split())
XY = [map(int, input().split()) for _ in range(M)]

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

x_to_y = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)


@lru_cache(N)
def depth(n):
    ret = -1
    for y in x_to_y[n]:
        ret = max(ret, depth(y))
    return ret + 1


        
depths = [depth(n) for n in range(1, N + 1)]
print(max(depths), default=0)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from functools import lru_cache

N, M = map(int, input().split())
XY = [map(int, input().split()) for _ in range(M)]

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

x_to_y = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)


@lru_cache(N)
def depth(n):
    ret = -1
    for y in x_to_y[n]:
        ret = max(ret, depth(y))
    return ret + 1


        
depths = [depth(n) for n in range(1, N + 1)]
print(max(depths))

Submission status: Runtime Error

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_g

G - Longest path

"""
import collections
import functools
import sys
sys.setrecursionlimit(100007)


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(pairs):
    adj_list = get_adj_list(pairs)

    @functools.lru_cache(100007)
    def dfs(u):
        res = -1
        for v in adj_list[u]:
            res = max(res, dfs(v))
        return 1 + res

    # depths = [dfs(u) for u in range(1, N+1)]
    # print(depths)
    depths = (dfs(u) for u in range(1, N+1))
    return max(depths, default=0)


N, M = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(M)]
res = solve(pairs)
print(res)

Submission status: Runtime Error

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_g

G - Longest path

"""
import collections
import functools
import sys
sys.setrecursionlimit(10000)


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(pairs):
    adj_list = get_adj_list(pairs)
    seen = set()

    @functools.lru_cache(10000)
    def dfs(u):
        seen.add(u)
        res = -1
        for v in adj_list[u]:
            if v not in seen:
                res = max(res, dfs(v))
        return 1 + res

    depths = [dfs(u) for u in range(1, N+1)]
    return max(depths)


N, M = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(M)]
res = solve(pairs)
print(res)

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
xy = [list(map(int,input().split())) for _ in range(M)]

dp = [None] * (N+1)

def get_dp(i):
    if dp[i] != None:
        return dp[i]
    yListSub = yList[i]
    if yListSub == []:
        dp[i] = 0
        return 0
    else:
        dp[i] = 1+ max(map(get_dp,yListSub))
        return dp[i]

yList = [[] for _ in range(N+1)]
for x,y in xy:
    yList[x].append(y)

[get_dp(i) for i in range(0,N+1)]
print(max(dp))

Submission status: Runtime Error

Solution code:
def get_kyori(i):
    if kos[i] == []:
        kyori[i] = 0
        return 0
    if kyori[i] > -1:
        return kyori[i]
    re = 0
    for ko in kos[i]:
        new = get_kyori(ko) + 1
        if re < new:
            re = new
    kyori[i] = re
    return re


n, m = map(int, input().split())
kos = [[] for _ in range(n + 1)]
kyori = [-1] * (n + 1)
for _ in range(m):
    oya, ko = map(int, input().split())
    kos[oya] += [ko]

for i in range(1, n + 1):
    if kyori[i] == -1:
        kyori[i] = get_kyori(i)

print(max(kyori[1:]))

Submission status: Runtime Error

Solution code:
def get_kyori(i):
    if kos[i]==[]:
        return 0
    if kyori[i]!=-1:
        return kyori[i]
    re=0
    for ko in kos[i]:
        new=get_kyori(ko)+1
        if re<new:
            re=new
    kyori[i]=re
    return re

n,m=map(int,input().split())
kos=[[] for _ in range(n+1)]
kyori=[-1]*(n+1)
for _ in range(m):
    oya,ko=map(int,input().split())
    kos[oya]+=[ko]

ans=0
for i in range(1,n+1):
    if kyori[i]==-1:
        kyori[i]=get_kyori(i)
    if kyori[i]>ans:
        ans=kyori[i]

print(ans)

Submission status: Runtime Error

Solution code:
def get_kyori(i):
    if kos[i]==[]:
        return 0
    if kyori[i]!=-1:
        return kyori[i]
    re=0
    for ko in kos[i]:
        new=get_kyori(ko)+1
        if re<new:
            re=new
    kyori[i]=re
    return re

n,m=map(int,input().split())
kos=[[] for _ in range(n+1)]
kyori=[-1]*(n+1)
for _ in range(m):
    oya,ko=map(int,input().split())
    kos[oya]+=[ko]

for i in range(1,n+1):
    if kyori[i]==-1:
        kyori[i]=get_kyori(i)

print(max(kyori[1:]))

Submission status: Runtime Error

Solution code:

import sys

MEMO = dict()

def search(n, data):
    global MEMO

    if n in MEMO:
        return MEMO[n]
    else:
        if not n in data:
            MEMO[n] = 0
            return 0

        MEMO[n] = max(search(i, data) for i in data[n]) + 1
        return MEMO[n]


def main():
    sys.setrecursionlimit(65535)
    N, M = map(int, input().split())
    data = dict()
    for _ in range(M):
        x, y = map(int, input().split())
        if x not in data:
            data[x] = [y]
        else:
            data[x].append(y)

    print(max(search(n, data) for n in range(1, N+1)))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/snap/bin/pypy3

MEMO = dict()

def search(n, data):
    global MEMO

    if n in MEMO:
        return MEMO[n]
    else:
        if not n in data:
            MEMO[n] = 0
            return 0

        MEMO[n] = max(search(i, data) for i in data[n]) + 1
        return MEMO[n]


def main():
    N, M = map(int, input().split())
    data = dict()
    for _ in range(M):
        x, y = map(int, input().split())
        if x not in data:
            data[x] = [y]
        else:
            data[x].append(y)

    print(max(search(n, data) for n in range(1, N+1)))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/snap/bin/pypy3

MEMO = dict()

def search(n, data):
    global MEMO
    
    if n in MEMO:
        return MEMO[n]
    else:
        startfrom_n = [element[1] for element in data if element[0] == n]
        if not startfrom_n:
            MEMO[n] = 0
            return 0

        MEMO[n] = max(search(i, data) for i in startfrom_n) + 1
        return MEMO[n]


def main():
    N, M = map(int, input().split())
    data = [tuple(map(int, input().split())) for _ in range(M)]


    print(max(search(n, data) for n in range(1, N+1)))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

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

graph = [[] for i in range(n + 1)]

for i in range(1, n + 1):
    graph[0].append(i)

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

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


def dfs(root):

    if len(graph[root]) == 0:
        dp[root] = 0

    for i in graph[root]:
        dfs(i)
        dp[root] = max(dp[root], 1 + dfs(i))

    return dp[root]


dfs(0)

print(dp[0]-1)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

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

graph = [[] for i in range(n + 1)]

for i in range(1, n + 1):
    graph[0].append(i)

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

dp = [-1] * (n + 1)


def dfs(root):

    if len(graph[root]) == 0:
        dp[root] = 0

    for i in graph[root]:
        dfs(i)
        dp[root] = max(dp[root], 1 + dp[i])

    return dp[root]


dfs(0)

print(dp[0]-1)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

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

graph = [[] for i in range(n + 1)]

for i in range(1, n + 1):
    graph[0].append(i)

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

dp = [-1] * (n + 1)


def dfs(root):
    if dp[root] != -1:
        return dp[root]

    if len(graph[root]) == 0:
        dp[root] = 0
        return 0

    for i in graph[root]:
        dp[root] = max(dp[root], 1 + dfs(i))

    return dp[root]


print(dfs(0)-1)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

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

graph = [[] for i in range(n + 1)]

for i in range(1, n + 1):
    graph[0].append(i)

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

dp = [-1] * (n + 1)


def dfs(root):
    if dp[root] != -1:
        return dp[root]

    if len(graph[root]) == 0:
        return 0

    for i in graph[root]:
        dp[root] = max(dp[root], 1 + dfs(i))

    return dp[root]


print(dfs(0)-1)

Submission status: Runtime Error

Solution code:
"""
考え方:
    頂点 n までの最大パスを, y = n である有向パスのすべての x の最大パス n' + 1 の中で最大のものから求める.
    x の最大パスが計算されていない場合は先に x の最大パスを同じ方法で求める.
    y = n となる有効パスが存在しない場合, n の最大パスは 0 とする. 有効閉路は存在しないのでループは発生しない.
    計算量は O(N + M) = O(2n) = O(n) .

提出1回目の反省:
    debug 用の print 外し忘れてた

提出2回目の反省:
    なぜ RE になるんじゃぁ
    -> python の最大再帰回数の問題である可能性. あんまりよくない気もするけど設定変更してみよう.
    
提出3回目の反省:
    10000 に設定してみたけどケース1_01ではじかれる. どうも設定値 - 1回目の呼び出しでエラーになるようだ.
    少し余裕をもって10020と設定.
"""

import sys
sys.setrecursionlimit(10020)


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

dp = [-1] * (N + 1)

def solve(num):
    re = 0
    if dp[num] != -1:
        # すでに計算済みのパスは再計算しない.
        re = dp[num]
    else:
        for x in Y[num]:
            if dp[x] == -1:
                dp[x] = solve(x)
            re = max(re, dp[x] + 1)
    return re

for n in range(1, N + 1):
    dp[n] = solve(n)

print(max(dp))

Submission status: Runtime Error

Solution code:
"""
考え方:
    頂点 n までの最大パスを, y = n である有向パスのすべての x の最大パス n' + 1 の中で最大のものから求める.
    x の最大パスが計算されていない場合は先に x の最大パスを同じ方法で求める.
    y = n となる有効パスが存在しない場合, n の最大パスは 0 とする. 有効閉路は存在しないのでループは発生しない.
    計算量は O(N + M) = O(2n) = O(n) .

提出1回目の反省:
    debug 用の print 外し忘れてた

提出2回目の反省:
    なぜ RE になるんじゃぁ
    -> python の最大再帰回数の問題である可能性. あんまりよくない気もするけど設定変更してみよう.

    
"""

import sys
sys.setrecursionlimit(10000)


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

dp = [-1] * (N + 1)

def solve(num):
    re = 0
    if dp[num] != -1:
        # すでに計算済みのパスは再計算しない.
        re = dp[num]
    else:
        for x in Y[num]:
            if dp[x] == -1:
                dp[x] = solve(x)
            re = max(re, dp[x] + 1)
    return re

for n in range(1, N + 1):
    dp[n] = solve(n)

print(max(dp))

Submission status: Runtime Error

Solution code:
"""
考え方:
    頂点 n までの最大パスを, y = n である有向パスのすべての x の最大パス n' + 1 の中で最大のものから求める.
    x の最大パスが計算されていない場合は先に x の最大パスを同じ方法で求める.
    y = n となる有効パスが存在しない場合, n の最大パスは 0 とする. 有効閉路は存在しないのでループは発生しない.
    計算量は O(N + M) = O(2n) = O(n) .

提出一回目の反省:
    debug 用の print 外し忘れてた
    
"""


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

dp = [-1] * (N + 1)

def solve(num):
    re = 0
    if dp[num] != -1:
        # すでに計算済みのパスは再計算しない.
        re = dp[num]
    else:
        for x in Y[num]:
            if dp[x] == -1:
                dp[x] = solve(x)
            re = max(re, dp[x] + 1)
    return re

for n in range(1, N + 1):
    dp[n] = solve(n)

print(max(dp))

Submission status: Runtime Error

Solution code:
"""
考え方:
    頂点 n までの最大パスを, y = n である有向パスのすべての x の最大パス n' + 1 の中で最大のものから求める.
    x の最大パスが計算されていない場合は先に x の最大パスを同じ方法で求める.
    y = n となる有効パスが存在しない場合, n の最大パスは 0 とする. 有効閉路は存在しないのでループは発生しない.
    計算量は O(N + M) = O(2n) = O(n) .
    
"""


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

dp = [-1] * (N + 1)

def solve(num):
    re = 0
    if dp[num] != -1:
        # すでに計算済みのパスは再計算しない.
        re = dp[num]
    else:
        for x in Y[num]:
            if dp[x] == -1:
                dp[x] = solve(x)
            re = max(re, dp[x] + 1)
    return re

for n in range(1, N + 1):
    dp[n] = solve(n)
    print(dp)

print(max(dp))

Submission status: Runtime Error

Solution code:
def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x-1].append(y-1)
        to_li[y-1].append(x-1)
    parents = []
    children = []
    dp = [-1]*N
    for index, to in enumerate(to_li):
        if len(to) == 0:
            parents.append(index)
    for index, fr in enumerate(from_li):
        if(len(fr)) == 0:
            children.append(index)
    print(max([g(to_li, from_li, parents, dp, c) for c in children]))

    
def g(to_li, from_li, parents, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n in parents:
        return 0
    val = max([g(to_li, from_li, parents, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

N, M = [int(x) for x in input().split()]
E = [[] for _ in range(N)]
for i in range(M):
    e = tuple([int(x) for x in input().split()])
    E[e[0] - 1].append(e[1] - 1)

dp = [-1] * N


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

    res = 0
    for n in E[v]:
        res = max(res, rec(n) + 1)
    dp[v] = res
    return res


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

print(res)