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:
import sys

def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = 0
    for b in xy[a]:
      if dp[b]:
        num = dp[b]
      else:
        num = cal(b)
        dp[b] = num
      if num+1 > ans:
        ans = num+1
    return ans
  return 0

if __name__ == "__main__":
  sys.setrecursionlimit(100000)
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()

Submission status: Accepted

Solution code:
from queue import Queue

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

E = [[] for i in range(n + 1)]
ind = [0] * (n + 1)
dp = [0] * (n + 1)
Q = Queue()
for i in range(m):
    x, y = map(int, input().split())
    E[x].append(y)
    ind[y] += 1

for i in range(1, n + 1):
    if not ind[i]:
        Q.put(i)

while not Q.empty():
    u = Q.get()
    for i in E[u]:
        ind[i] -= 1
        dp[i] = max(dp[i], dp[u] + 1)
        if not ind[i]:
            Q.put(i)

print(max(dp))

Submission status: Accepted

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

N,M=map(int, input().split())
A=[list(map(int, input().split())) for i in range(M)]
G=[[]for i in range(N)]
for a,b in A:
  G[a-1].append(b-1)
dp=[-1]*N

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

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

Submission status: Accepted

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

N,M=map(int, input().split())
A=[list(map(int, input().split())) for i in range(M)]
G=[[]for i in range(N)]
for a,b in A:
  G[a-1].append(b-1)
def chmax(a,b):
  if a>=b:
    return a
  else:
    return b
dp=[-1]*N
def rec(v):
  if dp[v]!=-1:
    return dp[v]
  ans=0
  for i in G[v]:
    ans=chmax(ans,rec(i)+1)
  dp[v]=ans
  return dp[v]
    
ans=0
for i in range(N):
  ans=chmax(ans,rec(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline
def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    else:
        return b
def main():  
    # 入力
    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)
    # 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 = chmax(ans, rec(nv) + 1)
        dp[v] = ans
        return dp[v]
    
    # 全ての点に対して更新する
    ans = 0
    for v in range(N):
        ans = chmax(ans, rec(v))
    
    print(ans)
main()

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(1000000)
dp = [-1]*(100*1000+1)
tab = [[] for x in range(100*1000+1)]

def get_max(root):
    if(dp[root] > -1): return dp[root]
    
    mi = 0
    for nei in tab[root]:
        mi = max(mi,get_max(nei)+1)
    dp[root] = mi
    return dp[root]
def main():
    n,m = map(int,input().split())
    
    for x in range(m):
        a,b = map(int,input().split())
        a-=1;b-=1
        tab[a].append(b)
    
    for x in range(n):
        get_max(x) 
    
    print(max(dp))
main()

Submission status: Accepted

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

N, M = input_nums()

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

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

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

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

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

Submission status: Accepted

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

n, m = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    x, y = map(lambda z: int(z)-1, input().split())
    G[x].append(y)

ans = [-1]*n
def dfs(i):
    if ans[i] != -1:
        return ans[i]
    if len(G[i]) == 0:
        ans[i] = 0
        return ans[i]
    res = 0
    for j in G[i]:
        res = max(res, dfs(j))
    ans[i] = res + 1
    return ans[i]

for i in range(n):
    dfs(i)

print(max(ans))

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys

sys.setrecursionlimit(10 ** 5 + 10)


# input = sys.stdin.readline


def resolve():
    # 入力
    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)
    # dp[v] := ノードvを始点とした時の有向パスの長さの最大値
    # -1 未訪問で初期化。
    dp = [-1] * N

    # メモ化再帰。rec(v)でvから行ける有向パスの長さを更新してゆく
    def rec(v):
        # 既に更新済み
        if dp[v] != -1:
            return dp[v]
        ans = 0
        lst_nv = lst_edge[v]
        # ノードvから直接行くことのできる各ノードnv
        for nv in lst_nv:
            ans = max(ans, rec(nv) + 1)
        # メモりつつリターン
        dp[v] = ans
        return dp[v]

    # 全ての点に対して更新する
    ans = 0
    for v in range(N):
        ans = max(ans, rec(v))

    print(ans)


resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

dp = [-1]*N

g = {}

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

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

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

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

print(ret)

Submission status: Accepted

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

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

dp = [-1] * n


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


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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

n, m = map(int, input().split())
path = [[] for i in range(n + 1)]
inbounds = [0] * (n + 1)

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

# Topological sort
topological = list(v for v in range(1, n + 1) if inbounds[v] == 0)
deq = deque(topological)

while deq:
    v = deq.popleft()
    for t in path[v]:
        inbounds[t] -= 1
        if inbounds[t] == 0:
            deq.append(t)
            topological.append(t)

# DP
dp = np.zeros(n + 1, dtype='int64')

for v in topological:
    for t in path[v]:
        dp[t] = max(dp[t], dp[v] + 1)

print(dp.max())

Submission status: Accepted

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

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

dp = [-1]*(N+5)
def rec(v):
    if dp[v] != -1:
        return dp[v]

    res = 0
    for nv in G[v]:
        if rec(nv) + 1 >= res:
            res = rec(nv) + 1
    dp[v] = res
    return res
ans = 0
for v in range(N):
    ans = max(ans, rec(v))
print(ans)

Submission status: Accepted

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

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

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

dp = [None] * N
for node in range(N):
    if has_no_child[node]:
        dp[node] = 0

for node in range(N):
    if dp[node] is not None:
        continue
    stack = []
    stack.append(node)
    while stack:
        parent = stack[-1]
        all_children_defined = True
        for child in children[parent]:
            if dp[child] is None:
                stack.append(child)
                all_children_defined = False
        if all_children_defined:
            stack.pop()
            dp[parent] = max([dp[child] + 1 for child in children[parent]])

print(max(dp))

Submission status: Accepted

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

dp = [-1] * N

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

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

print(max(dp))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

lp = [None] * N
for node in range(N):
    if has_no_child[node]:
        lp[node] = 0

def dp(node):
    if lp[node] is not None:
        return lp[node]
    result = max([dp(child) + 1 for child in children[node]])
    lp[node] = result
    return result

for node in range(N):
    if lp[node] is None:
        dp(node)

print(max(lp))

Submission status: Accepted

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

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


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


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


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


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


mod = int(1e9)+7


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


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

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



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


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

Submission status: Accepted

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

n,m=map(int,input().split())
to=[[] for i in range(n)]

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def topological_sort(G):
    ret = []
    start = []
    parent = [set() for _ in range(len(G))]
    for u in range(len(G)):
        for v in G[u]:
            parent[v].add(u)
    for v in range(len(G)):
        if not parent[v]:
            start.append(v)

    while start:
        u = start.pop()
        ret.append(u)
        for v in G[u]:
            parent[v].remove(u)
            if not parent[v]:
                start.append(v)

    if any(parent):
        # G is not DAG
        return None
    return ret

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
parent = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    parent[y].append(x)
V = topological_sort(G)
dp = [0] * (N+1)
for i in V:
    for j in parent[i]:
        dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque
N,M = list(map(int,input().split()))
inflows = [0]*(N+1)
edges = [[] for i in range(N+1)]
for i in range(M):
    x,y = list(map(int,input().split()))
    edges[x].append(y)
    inflows[y] += 1

queue = deque([i for i in range(1,N+1) if inflows[i] == 0])
DP = [0]*(N+1)
while queue:
    x = queue.popleft()
    for y in edges[x]:
        inflows[y] -= 1
        DP[y] = max(DP[y],DP[x]+1)
        if inflows[y] == 0:
            queue.append(y)

print(max(DP))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
path = [0 for i in range(n+1)]
con = [0 for i in range(n+1)]
for a,b in ab:
  graph[b].append(a)
  path[a] = -1
  con[a] += 1
stack = []
for i in range(1,n+1):
  if path[i] == 0:
    stack.append(i)
    while stack:
      x = stack.pop()
      for y in graph[x]:
        path[y] = max(path[y],path[x]+1)
        con[y] -= 1
        if con[y] == 0:
          stack.append(y)
print(max(path))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
adj = {}
indegrees = [0 for _ in range(n+1)]
for _ in range(m):
  cur, nxt = map(int, input().split())
  adj[cur] = adj.get(cur, []) + [nxt]
  indegrees[nxt] += 1
  
stack = []
for i in range(1, n+1):
  if indegrees[i] == 0:
    stack.append(i)
    
dp = [0 for _ in range(n+1)]
    
while stack:
  cur = stack.pop()
  for nxt in adj.get(cur, []):
    indegrees[nxt] -= 1
    if indegrees[nxt] == 0:
      stack.append(nxt)
    dp[nxt] = max(dp[nxt], dp[cur] + 1)
print(max(dp))

Submission status: Accepted

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

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

print(max(dp))

Submission status: Accepted

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

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

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

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

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

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

print(max(dp))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int,input().split())
    edge = [[] for i in range(n)]
    #st:入る辺が無い頂点
    st = []
    #to[i]:頂点iに入る辺数
    to = [0]*n
    for i in range(m):
        x,y = map(int, input().split())
        edge[x-1].append(y-1)
        to[y-1] += 1
    for i in range(n):
        if to[i] == 0:
            st.append(i)

    #dp[i]:頂点iを終点とする最長のパスの長さ
    dp = [0]*n
    while st:
        go = st.pop()
        for e in edge[go]:
            to[e] -= 1
            if to[e] == 0:
                st.append(e)
            dp[e] = max(dp[e],dp[go]+1)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#トポロジカルソートなるもの
#再帰で書いてるところをwhileで書いてる
#要は無駄な探索(再帰呼び出し)を無くしてる
#まぁ思いつかない

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int,input().split())
    edge = [[] for i in range(n)]
    #st:入る辺が無い頂点
    st = []
    #to[i]:頂点iに入る辺数
    to = [0]*n
    for i in range(m):
        x,y = map(int, input().split())
        edge[x-1].append(y-1)
        to[y-1] += 1
    for i in range(n):
        if to[i] == 0:
            st.append(i)

    #dp[i]:頂点iを終点とする最長のパスの長さ
    dp = [0]*n
    while st:
        go = st.pop()
        for e in edge[go]:
            to[e] -= 1
            if to[e] == 0:
                st.append(e)
            dp[e] = max(dp[e],dp[go]+1)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

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

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n , m = map(int,input().split())

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

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

def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp = 0
  for neighbour in g[i]:
    temp = max(temp, dfs(neighbour) + 1)
  dp[i]=temp
  return temp
  
res = 0
for i in range(n):
  res = max(res, dfs(i))

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque

N,M=map(int,input().split())
Out=defaultdict(list)
In=defaultdict(int)

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

q=deque(v for v in range(1,N+1) if In[v]==0)

dp=[0]*(N+1)

while q:
    From = q.popleft()
    for to in Out[From]:
        dp[to]=max(dp[From]+1,dp[to])
        In[to]-=1
        if In[to]==0:
            q.append(to)
print(max(dp))

Submission status: Accepted

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

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

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

    tmp = 0
    for j in g[i]:
        tmp = max(tmp, dfs(j) + 1)

    dp[i] = tmp
    return tmp

for i in range(n):
    dfs(i)

print(max(dp))

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,M = imn()
G = [[] for _ in range(N)]
dp = [-1 for _ in range(N)]

for i in range(M):
    xy = iln()
    G[xy[0]-1].append(xy[1]-1)

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

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

Submission status: Accepted

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

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

dp = [-1] * N
def dfs(v):
    if dp[v] > -1:
        return dp[v] + 1
    ret = 0
    for i in path[v]:
        ret = max(ret, dfs(i))
    dp[v] = ret
    return ret + 1


for i in range(N):
    if dp[i] < 0:
        dfs(i)

print(max(dp))

Submission status: Accepted

Solution code:
"""memo
    トポロジカルソート「http://zehnpaard.hatenablog.com/entry/2018/06/26/201512」
    をしてから，dpで求めた．（ソートと同時にdp求められそう）
"""
from collections import deque, defaultdict
import sys
input == sys.stdin.readline

def main():
    v, n = map(int, input().split())
    es = [[int(x) for x in input().split()] for _ in range(n)]

    outs = defaultdict(list)
    ins = defaultdict(int)
    #print(ins)
    for v1, v2 in es:
        outs[v1].append(v2)
        ins[v2] += 1
        #print(ins)
    #print("be",ins)
    q = deque(v1 for v1 in range(1,v+1) if ins[v1] == 0) #rangeは無駄なものがない
    #print("af",ins)
    res = []
    #print(outs)
    #print(ins)
    dp = [0]*(v+1)
    while q:
        #print(q)
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
            dp[v2] = dp[v1] + 1
            #print("-->",v2)
            ins[v2] -= 1
            if ins[v2] == 0: #v2のノードに入る矢印をすべて見たときにqに追加
                #print("<--",v2)
                q.append(v2)
    #print(res[1:])
    #print(outs)
    #print(ins)

    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

v, n = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(n)]

outs = defaultdict(list)
ins = defaultdict(int)
#print(ins)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
    #print(ins)
#print("be",ins)
q = deque(v1 for v1 in range(v+1) if ins[v1] == 0)
#print("af",ins)
res = []
#print(outs)
#print(ins)
while q:
    #print(q)
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        #print("-->",v2)
        ins[v2] -= 1
        if ins[v2] == 0:
            #print("<--",v2)
            q.append(v2)
#print(res[1:])
#print(outs)
#print(ins)

dp = [0]*(v+1)
for i in res[1:]:
    for j in outs[i]:
        dp[j] = dp[i] + 1
        #print(i, j, dp)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100002)


N, M = map(int, input().split())
g = {}
for i in range(N):
    g[i] = set()
for _ in range(M):
    pre, post = map(int, input().split())
    g[post-1].add(pre-1)    # reversed

# dp[i 頂点まで使って][j 頂点を終端とする] = 最長有向パス
dp = [-1 for _ in range(N)]


def dp_rec(p):

    if dp[p] != -1:
        return dp[p]

    res = 0
    for n in g[p]:
        res = max(res, dp_rec(n) + 1)

    dp[p] = res
    return res


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

Submission status: Accepted

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

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

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

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

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


def calc(x):
    if lst[x] != -1:
        return lst[x]
    tmp = 0
    for next_ in G[x]:
        tmp = max(tmp, calc(next_))
    
    lst[x] = tmp + 1
    return tmp + 1

ans = 0
for i in range(1, N + 1):
    if lst[i] == -1:
        ans = max(ans, calc(i))

print (ans - 1)

Submission status: Accepted

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

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

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

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

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


def calc(x):
    if lst[x] != -1:
        return lst[x]
    tmp = 0
    for next_ in G[x]:
        tmp = max(tmp, calc(next_))
    
    lst[x] = tmp + 1
    return tmp + 1

for i in range(1, N + 1):
    if lst[i] == -1:
        calc(i)

print (max(lst) - 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


def main():
    n, m = map(int, input().split())

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

    def longest(i, memo):
        if memo[i] >= 0:
            return memo[i]
        if len(net[i]) == 0:
            l = 0
        else:
            l = max(longest(j, memo) + 1 for j in net[i])
        memo[i] = l
        return l

    memo = [-1] * n
    l = max(longest(i, memo) for i in range(n))
    print(l)


main()

Submission status: Accepted

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

from collections import defaultdict
from collections import deque
from collections import Counter
g = defaultdict(set)

for x, y in XY:
  g[x].add(y)
  
  
def TSort(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    funin = Counter()
    
    for u in V:
        for v in g[u]:
            funin[v] += 1
    
    q = deque()
    for v in V:
        if funin[v] == 0:
            q.append(v)
    L = []
    while q:
        u = q.popleft()
        L.append(u)
        for v in g[u]:
            funin[v] -= 1
            if funin[v] == 0:
                q.append(v)
    return L

  
D = Counter()
ns = TSort(g)
for u in ns:
  for v in g[u]:
    D[v] = max(D[v], D[u] + 1)
print(D.most_common()[0][1])

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10000000)

N,M = map(int,input().split())
A = [list(map(int, input().split())) for i in range(M)]
visit = set()
G = collections.defaultdict(set)
for idx,(f,to) in enumerate(A):
    G[f].add(to)

cache = {}
    
def dfs(start):
    if start in cache:
        return cache[start]
    ma = 0
    for i in G[start]:
        if i not in visit:
            #visit.add(i)
            ma = max(ma,dfs(i))
            #visit.remove(i)
    cache[start] = ma + 1 
    return ma + 1

ma = 0 
for f,to in A:
    #visit.add(f)
    ma = max(ma,dfs(f))
    #visit.remove(f)
print(ma - 1)

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10000000)

N,M = map(int,input().split())
A = [list(map(int, input().split())) for i in range(M)]
visit = set()
G = collections.defaultdict(set)
for idx,(f,to) in enumerate(A):
    G[f].add(to)

cache = {}
    
def dfs(start):
    if start in cache:
        return cache[start]
    ma = 0
    for i in G[start]:
        if i not in visit:
            visit.add(i)
            ma = max(ma,dfs(i))
            visit.remove(i)
    cache[start] = ma + 1 
    return ma + 1

ma = 0 
for f,to in A:
    visit.add(f)
    ma = max(ma,dfs(f))
    visit.remove(f)
print(ma - 1)