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: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 14:22:54 2020

@author: Maruthi Srinivas
"""
import sys
sys.setrecursionlimit(1000000)
def dfs(node,graph,dp):
    temp=0
    if dp[node]!=-1:
        return dp[node]
    for i in graph[node]:
        temp=max(temp,dfs(i,graph,dp)+1)
    dp[node]=temp
    return temp
            
v,e=map(int,input().split())
adj={x:[] for x in range(v+1)}
for i in range(e):
    x,y=map(int,input().split())
    adj[x].append(y)
m=-1
dp=[-1]*(v+1)
for i in range(1,v+1):
    x=dfs(i,adj,dp)
    m=max(m,x)
print(m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    edge[x].append(y)
flag=[0]*n
dp=[0]*n
def dfs(s):
    if flag[s]:
        return dp[s]
    flag[s]=1
    dist=0
    for i in edge[s]:
        dist=max(dist,dfs(i)+1)
    dp[s]=dist
    return dp[s]
for i in range(n):
    dfs(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
from collections import *
sys.setrecursionlimit(10**5)
def dfs(x):
    visited[x]=True
    for i in range(len(adj[x])):
        t=adj[x][i]
        distance[t]=max(distance[t],distance[x]+1)
        indegree[t]-=1
        if(indegree[t]==0):
            dfs(t)

MAX = 10**5+5
indegree=[0]*(MAX)
distance=[0]*(MAX)
visited = [False]*(MAX)
adj = defaultdict(list)
N,M=list(map(int,input().split()))
for i in range(M):
    a,b=list(map(int,input().split()))
    adj[a].append(b)
    indegree[b]+=1
ans=0
for i in range(1,N+1):
    if(visited[i]==False and indegree[i]==0):
        dfs(i)
for i in range(1,N+1):
    ans=max(ans,distance[i])

print(ans)

Submission status: Accepted

Solution code:
import sys


def resolve():
    sys.setrecursionlimit(10 ** 6)
    readline = sys.stdin.readline
    
    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 dp[v]

    N, M = map(int, readline().split())
    G = [[] for _ in [0] * N]
    for _ in [0] * M:
        x, y = map(int, readline().split())
        G[x - 1].append(y - 1)

    # メモ化再帰
    dp = [-1] * N
    res = 0
    for v in range(N):
        res = max(res, rec(v))
    print(res)


resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

def dfs(x):
  if x in memo:
    return memo[x]
  ret=0
  for y in g[x]:
    ret=max(ret,dfs(y)+1)
  memo[x]=ret
  return ret

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
memo={}
for i in range(1,n+1):
  dfs(i)
print(max(memo.values()))

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        e[a - 1].append(b - 1)

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

    def dfs(ti):
        tmp = 0
        for vi in e[ti]:
            if res[vi] != -1:
                tmp = max(tmp, res[vi] + 1)
            else:
                tmp = max(tmp, dfs(vi) + 1)
        res[ti] = tmp
        return tmp

    ans = 0
    for i in range(n):
        if res[i] == -1:
            ans = max(ans, dfs(i))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+1)

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

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

def judge(index):
  if dp[index] != -1:
    return dp[index]
  else:
    edges = 0
    for i in nodes[index]:
      edges = max(edges, 1+judge(i))
    dp[index] = edges
    return edges

answer = 0
for i in range(N):
  answer = max(answer, judge(i))
print(answer)

Submission status: Accepted

Solution code:
import sys

global N, M
global edgeList

global longestPathFrom

def dfs(x):
    if longestPathFrom[x] == -1:
        # get
        longest = -1
        for nextNode in edgeList[x]:
            longest = max(longest, dfs(nextNode))
        # set
        if longest == -1:
            longestPathFrom[x] = 0
        else:
            longestPathFrom[x] = longest + 1
    # -- longest path from x has been calculated
    return longestPathFrom[x]

# -- main
if __name__ == '__main__':
    # -- 
    sys.setrecursionlimit(1000001)

    # -- input
    N, M = map(int, input().split())
    edgeList = [[] for node in range(N)]

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

    # -- process
    longestPathFrom = [-1] * N

    for node in range(N):
        if longestPathFrom[node] == -1:
            dfs(node)

    # -- output
    print(max(longestPathFrom))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5 + 1)

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

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

dp = [-1] * N

def judge(index):
  if dp[index] != -1:
    return dp[index]
  else:
    edges = 0
    for i in nodes[index]:
      edges = max(edges, 1+judge(i))
    dp[index] = edges
    return edges

answer = 0  
for i in range(N):
  answer = max(answer, judge(i))
print(answer)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
from collections import defaultdict


g = None


@lru_cache(100000)
def f(x):
    ret = 0
    for y in g[x]:
        ret = max(ret, f(y) + 1)
    return ret


def resolve(in_):
    global g
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    f.cache_clear()
    return max(f(i) for i in range(n))


def main():
    sys.setrecursionlimit(1000000)
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


g = None
memo = None


def f(x):
    if memo[x] == -1:
        ret = 0
        for y in g[x]:
            ret = max(ret, f(y) + 1)
        memo[x] = ret
    return memo[x]


def resolve(in_):
    global g, memo
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    memo = [-1] * 100000
    return max(f(i) for i in range(n))


def main():
    sys.setrecursionlimit(1000000)
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
arrive=[0]*n
ready=[]
for i in range(m):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    arrive[y-1]+=1
for i in range(n):
    if arrive[i]==0:
        ready.append(i)

path_num=[0]*n
while ready:
    depart=ready.pop()
    for to in edge[depart]:
        path_num[to]=max(path_num[to],path_num[depart]+1)
        arrive[to]-=1
        if arrive[to]==0:
            ready.append(to)
print(max(path_num))

Submission status: Accepted

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

n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    for j in range(2):
        C[i][j] -= 1

D = [0] * n
M = [[] for i in range(n)]
for i in range(m):
    M[C[i][0]].append(C[i][1])

IN = [0] * n
for i in range(m):
    IN[C[i][1]] += 1

S = []
s = 0

for i in range(n):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        if IN[x] == 0:
            S.append(x)
    s += 1



for i in range(n):
    for j in range(len(M[S[i]])):
        D[M[S[i]][j]] = max(D[M[S[i]][j]], D[S[i]] + 1)
print(max(D))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 1)
N,M = map(int,input().split())

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

dp = [-1] * N # dp[i] = 頂点iから進むことが出来る深さ
def search(v):
  if dp[v] != -1:
    return dp[v]
  max_depth = 0
  for child in G[v]:
    max_depth = max(max_depth, search(child) + 1)
    
  dp[v] = max(dp[v], max_depth)
  return dp[v]

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

print(max(dp))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

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

def rec(v,visited,order):
    visited[v] = 0
    for u in adj[v]:
        if visited[u] < 0:
            rec(u,visited,order)
    order.append(v)

def main():
    xy = []
    for _ in range(M):
        x, y = map(int, input().split())
        xy.append((x-1,y-1))
        adj[x-1].append(y-1)
    
    # トポロジカルソート（dfsによって実装）
    visited = [-1] * N
    order = []
    for i in range(N):
        if visited[i] < 0:
            rec(i,visited,order)

    # 自分を始点とするパスの最長を保存
    dp = [0]*(N+1)
    for o in order:
        for u in adj[o]:
            dp[o] = max(dp[o],dp[u]+1)
    
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

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

G = [[] for i in range(N)]

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

dp = [-1] * N

def rec(v):
  if dp[v] != -1:
    return dp[v] # 更新済み
  
  res = 0
  for child in G[v]:
    res = max(res, rec(child) + 1)
    
  dp[v] = res
  return res

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

def resolve():
    def rec(v):
        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

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

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**7)
def LPP():
    n, m = map(int, readline().split())
    edges = [[] for _ in range(n)]
    for _ in range(m):
        s, t = map(int, readline().split())
        s -= 1
        t -= 1
        edges[s].append(t)
    dp = [-1]*n
    def dfs(s):
        if dp[s] != -1:
            return dp[s]
        if len(edges[s]) == 0:
            dp[s] = 0
            return 0
        res = 0
        for t in edges[s]:
            res = max(res, dfs(t)+1)
        dp[s] = res
        return res
    for i in range(n):
        dfs(i)
    print(max(dp),end="")

LPP()

Submission status: Accepted

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

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

G = [[] for i in range(N)]
indegree = [0] * N

for i in range(M):
  x,y = map(int,readline().split())
  G[x - 1].append(y - 1)
  indegree[y - 1] += 1
  
start = set()
for i in range(len(indegree)):
  if indegree[i] == 0:
    start.add(i)
    
cnt = 0
while start:
  nex = set()
  hasnext = False
  for s in start:
    for y in G[s]:
      indegree[y] -= 1
      if indegree[y] == 0:
        nex.add(y)
        hasnext = True
  if hasnext:
    cnt += 1
  start = nex

print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

G = []
dp = []

def rec(v):
    global dp
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for node in G[v]:
        ans = max(ans, rec(node) + 1)
    dp[v] = ans
    return dp[v]

def main():
    global G, dp
    n, m = list(map(int, input().strip().split()))
    G = [[] for _ in range(n)]
    dp = [-1] * n
    for i in range(m):
        p, q = list(map(int, input().strip().split()))
        p -= 1
        q -= 1
        G[p].append(q)
    ans = 0
    for i in range(n):
        r = rec(i)
        # print("r: ", r)
        ans = max(ans, r)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[0]*n
indegree=[0]*n
edges=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  indegree[b-1]+=1
  edges[a-1].append(b-1)
  
starting=[]
for i in range(n):
  if(indegree[i]==0):
  	starting.append(i)
visited=set()
#print(edges)
#print(starting)
while starting:
  #print(starting)
  #print(dp)
  start=starting.pop()
  end=edges[start]
  for j in end:
    dp[j]=max(dp[j],dp[start]+1)
    indegree[j]-=1
    if(indegree[j]==0):
      starting.append(j)
print(max(dp))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [0] * n
indeg = [0] * n
to = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    to[x].append(y)
    indeg[y] += 1
avail = list(filter(lambda i: indeg[i] == 0, range(n)))
while avail:
    u = avail.pop()
    for v in to[u]:
        dp[v] = max(dp[v], dp[u] + 1)
        indeg[v] -= 1
        if indeg[v] == 0:
            avail.append(v)
print(max(dp))

Submission status: Accepted

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


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    edge[s].append(t)

dp = [-1]*N

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    if len(edge[s]) == 0:
        dp[s] = 0
        return 0
    res = 0
    for t in edge[s]:
        res = max(res, dfs(t)+1)
    dp[s] = res
    return res

for i in range(N):
    dfs(i)
print(max(dp))

Submission status: Accepted

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

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
deg = [0 for _ in range(N)]
dp = [0 for _ in range(N)]

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

stack = []

for i in range(N):
    if not deg[i]:
        stack.append(i)

while stack:
    node = stack.pop()
    for adj in graph[node]:
        deg[adj] -= 1
        dp[adj] = max(dp[adj], dp[node] + 1)
        if not deg[adj]:
            stack.append(adj)

print(max(dp))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def get_longest(x, longest, edges):
    if longest[x] is not None:
        return longest[x]
    if not edges[x]:
        longest[x] = 0
    else:
        result = max([get_longest(y, longest, edges)
                      for y in edges[x]])
        longest[x] = result + 1
    return longest[x]


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    edges = defaultdict(set)
    for i in range(M):
        x, y = map(int, input().split())
        edges[x].add(y)

    longest = [None] * (N + 1)
    for x in range(N):
        x += 1
        if longest[x] is None:
            get_longest(x, longest, edges)

    print(max(longest[1:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)


def main():
    def DFS(v):
        if DP[v] == -1:
            res = 0
            for i in G[v]:
                res = max(res, DFS(i) + 1)

            DP[v] = res

        return DP[v]


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

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

    DP = [-1] * N
    for v in range(N):
        DFS(v)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Submission status: Accepted

Solution code:
from collections import deque


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

    G = [[] for _ in range(N)]
    ins = [0] * N
    for x, y in xy:
        G[x - 1].append(y - 1)
        ins[y - 1] += 1

    DP = [0] * N
    queue = deque()
    for i in range(N):
        if ins[i] == 0:
            queue.append(i)

    while queue:
        v = queue.popleft()
        for i in G[v]:
            ins[i] -= 1
            if ins[i] == 0:
                DP[i] = max(DP[i], DP[v] + 1)
                queue.append(i)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys
import numpy as np
import numba

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


@numba.njit(cache=True)
def get_longest(start, values, next, head, longest):
    ret = longest[start]
    if ret != -1:
        return ret

    ret = 0
    p = head[start]
    while p:
        v = values[p]
        x = get_longest(v, values, next, head, longest) + 1
        if x > ret:
            ret = x
        p = next[p]

    longest[start] = ret
    return ret


@numba.njit(cache=True)
def solve(N, M, data):
    longest = np.repeat(-1, N + 1)

    values = np.zeros(M + 1, np.int32)
    next = np.zeros(M + 1, np.int32)
    head = np.zeros(N + 1, np.int32)
    p = 1
    for i in range(0, 2 * M, 2):
        v1 = data[i]
        v2 = data[i + 1]
        values[p] = v2
        next[p] = head[v1]
        head[v1] = p
        p += 1

    for i in range(N + 1):
        if head[i] == 0:
            longest[i] = 0

    ret = 0
    for v in range(N + 1):
        x = get_longest(v, values, next, head, longest)
        if x > ret:
            ret = x
    return ret


def main():
    N, M = map(int, input().split())
    data = np.int32(read().split())
    print(solve(N, M, data))


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def _test():
    """
    # >>> as_input(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    # from numba.pycc import CC
    # cc = CC('my_module')
    # cc.export(
    #     'solve',
    #     "i4(i4,i4,i4[:])")(solve)
    # cc.export(
    #     'get_longest',
    #     "i4(i4,i4[:],i4[:],i4[:],i4[:])")(get_longest)
    # cc.compile()
    import numba
    numba.njit(cache=True)(get_longest)
    numba.njit(cache=True)(solve)
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all

    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
from collections import deque


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

    G = [[] for _ in range(N)]
    ins = [0] * N
    for i in range(M):
        G[xy[i][0] - 1].append(xy[i][1] - 1)
        ins[xy[i][1] - 1] += 1

    DP = [0] * N
    queue = deque()
    for i in range(N):
        if ins[i] == 0:
            queue.append(i)

    while queue:
        v = queue.popleft()
        for i in G[v]:
            ins[i] -= 1
            if ins[i] == 0:
                DP[i] = max(DP[i], DP[v] + 1)
                queue.append(i)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = [-1] * (N + 1)
    for i in range(N + 1):
        if not edges[i]:
            longest[i] = 0

    def get_longest(start):
        next = edges[start]
        for v in next:
            if longest[v] == -1:
                longest[v] = get_longest(v)

        ret = max(longest[v] for v in next) + 1
        return ret

    for i in range(N + 1):
        if longest[i] == -1:
            longest[i] = get_longest(i)

    return max(longest[v] for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = {}

    stack = [v for v in edges]

    while stack:
        v = stack.pop()
        if v > 0:
            if v in longest:
                continue
            next_edges = edges.get(v)
            stack.append(-v)
            if next_edges:
                stack.extend(next_edges)
        else:
            next_edges = edges.get(-v)
            if not next_edges:
                ret = 0
            else:
                ret = max(longest[x] for x in next_edges) + 1
            longest[-v] = ret

    return max(longest[v] for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def _test():
    """
    # >>> as_input(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys
import numpy as np
import numba

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


@numba.njit
def get_longest(start, values, next, head, longest):
    ret = longest[start]
    if ret != -1:
        return ret

    ret = 0
    p = head[start]
    while p:
        v = values[p]
        x = get_longest(v, values, next, head, longest) + 1
        if x > ret:
            ret = x
        p = next[p]

    longest[start] = ret
    return ret


@numba.njit
def solve(N, M, data):
    longest = np.repeat(-1, N + 1)

    values = np.zeros(M + 1, np.int32)
    next = np.zeros(M + 1, np.int32)
    head = np.zeros(N + 1, np.int32)
    p = 1
    for i in range(0, 2 * M, 2):
        v1 = data[i]
        v2 = data[i + 1]
        values[p] = v2
        next[p] = head[v1]
        head[v1] = p
        p += 1

    for i in range(N + 1):
        if head[i] == 0:
            longest[i] = 0

    ret = 0
    for v in range(N + 1):
        x = get_longest(v, values, next, head, longest)
        if x > ret:
            ret = x
    return ret


def main():
    N, M = map(int, input().split())
    data = np.int32(read().split())
    print(solve(N, M, data))


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def _test():
    """
    # >>> as_input(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    import numba
    cc = CC('my_module')
    cc.export(
        'solve',
        numba.i8(
            numba.i8, numba.i8,
            numba.typeof({1: [1]})))(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def cal(e):
    if ans_array[e] != -1:
        return ans_array[e]
    ans = 0
    if e in node_dic:
        for x in node_dic[e]:
            ans = max(ans, cal(x) + 1)
    ans_array[e] = ans
    return ans


N, M = na()
node_dic = {}
no_in = [1] * N

for _ in range(M):
    x, y = na()
    if x-1 in node_dic:
        node_dic[x-1].append(y-1)
    else:
        node_dic[x-1] = [y-1]
    no_in[y-1] = 0


# print(node_dic, no_in)


ans_array = [-1] * N

edge = deque([])

for i, x in enumerate(no_in):
    if x == 1:
        cal(i)


print(max(ans_array))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
Cython test
"""
from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, M, edges):
    longest = [-1] * (N + 1)

    def get_longest(start):
        if longest[start] != -1:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


def _test():
    """
    # >>> as_input(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()