Problem p03166 (python)

Fixed submission:
from collections import defaultdict, deque

def topological_sort(vertex:list, edge:list):
    graph = {i: [] for i in vertex}
    for i, j in edge:
        graph[i].append(j)
        
    inp_cnt = defaultdict(int)
    outs = defaultdict(list)
    for inp, out in edge:
        inp_cnt[out] += 1
        outs[inp].append(out)

    result = []
    queue = deque([i for i in vertex if inp_cnt[i]==0])
    while queue:
        v = queue.popleft()
        result.append(v)
        for v2 in outs[v]:
            inp_cnt[v2] -= 1
            if inp_cnt[v2] == 0:
                queue.append(v2)
    return result

N, M = map(int, input().split())
vertex = list(range(1, N+1))
edge = [list(map(int, input().split())) for _ in range(M)]
graph = {i: [] for i in vertex}
for i, j in edge:
    graph[i].append(j)

sorted_vertecies = topological_sort(vertex, edge)
dp = [0] * (N+1)
for i in sorted_vertecies:
    ends = graph[i]
    for j in ends:
        dp[j] = max(dp[j], dp[i] + 1)
print(max(dp))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

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

g = {i:[] for i in range(1, 110000)}
g2 = {i:[] for i in range(1, 110000)}
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp2(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

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

g = {i:[] for i in range(110000)}
g2 = {i:[] for i in range(110000)}
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp_2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp2(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

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

g = defaultdict(list)
g2 = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp2(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

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

g = defaultdict(list)
g2 = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)
    g2[y].append(x)

def dp_2(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    
    for i in g2[v]:
        max_len = max(max_len, dp(i) + 1)
    done[v] = 1
    memo[v] = max_len
    return max_len
    
    
def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

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

g = defaultdict(list)
done = [0] * (N+50)
memo = [0] * (N+50)
for x, y in xy:
    g[x].append(y)

def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

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

g = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)
for x, y in xy:
    g[x].append(y)

def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
        return max_len

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

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

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

g = defaultdict(list)
done = [0] * (N+1)
memo = [0] * (N+1)

for x, y in xy:
    g[x].append(y)

def dp(v):
    max_len = 0
    if done[v] == 1:
        return memo[v]
    else:
        for to in g[v]:
            max_len = max(max_len, dp(to)+1)
        done[v] = 1
        memo[v] = max_len
    return max_len

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