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

# 許容する再帰処理の回数を変更
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 sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=[[]for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    s[a-1].append(b-1)
k=[-1]*n
def dfs(v):
    if k[v]!=-1:
        return k[v]
    k[v]=r=max(dfs(q)for q in s[v])+1 if s[v] else 0
    return r
print(max(dfs(t)for t in range(n)))

Submission status: Accepted

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と設定.

提出4回目の反省:
    それでもケース1_01がダメ. なぜ...
    
"""

import sys
sys.setrecursionlimit(10 ** 6)


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

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

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)
    
memo = [-1] * N
def dfs(v):
    if memo[v] == -1:
        memo[v] = max(dfs(w) for w in G[v]) + 1 if G[v] else 0
    return memo[v]
print(max(dfs(v) for v in range(N)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def main():
    n, m = [int(n) for n in input().split()]
    paths = [[] for i in range(n+1)]
    for i in range(m):
        x, y = [int(r) for r in input().split()]
        paths[x].append(y)
    dp = [-1]*(n+1)

    ans = 0
    for i in range(n+1):
        ans = max(ans, dfs(paths, dp, i))
    print(ans-1)
def dfs(paths, dp, n):
    # nから下の最大長
    length = 0
    for p in paths[n]:
        val=0
        if dp[p] != -1:
            val = dp[p]
        else:
            val = dfs(paths, dp, p)
        length = max(length, val)
    length += 1 # pからnまでの一本もしくはnから終点までの一本
    dp[n] = length
    return length

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n, m = map(int, input().split())
xy = [tuple(int(x)-1 for x in input().split()) for _ in range(m)]

R = [[] for _ in range(n)]
h = [0] * n

for x, y in xy:
    R[x].append(y)
    h[y] += 1

S = []

st = []

for i in range(n):
    if h[i] == 0:
        heappush(st, i)

while len(st) > 0:
    temp = heappop(st)
    S.append(temp)
    for x in R[temp]:
        h[x] -= 1
        if h[x] == 0:
            heappush(st, x)

#print(S)

dp = [0] * n

for x in S:
    for y in R[x]:
        dp[y] = max(dp[y], dp[x] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
edges=[[] for _ in range(n)]
S=[]
T=[0]*n
for _ in range(m):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    T[y-1]+=1
for i in range(n):
    if T[i]==0:
        S.append(i)
DP=[0]*n
while S:
    fr=S.pop()
    for to in edges[fr]:
        T[to]-=1
        if T[to]==0:
            S.append(to)
        DP[to]=max(DP[to],DP[fr]+1)
print(max(DP))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_g
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)

# BFS版
from collections import deque


deg = [0] * N  # 各頂点の入力数
dp = [0] * N   # 各頂点のスタートからの距離

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

que = deque([i for i, v in enumerate(deg) if v == 0])

while len(que) > 0:
    v = que.popleft()
    for to in E[v]:
        deg[to] -= 1
        if deg[to] == 0:
            que.append(to)
            dp[to] = max(dp[to], dp[v] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(100000)

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:i -= 1
        elif dp[i][j] == dp[i][j-1]:j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)
#G
def G():
    def dfs(x):
        if dp[x] != None:
            return dp[x]
        if len(v[x]) == 0:
            dp[x] = 0
            return 0
        else:
            res = 0
            for y in v[x]:
                res = max(res,dfs(y)+1)
            dp[x] = res
            return dp[x]
    n,m = LI()
    dp = [None for i in range(n)]
    v = [[] for i in range(n)]
    for i in range(m):
        x,y = LI()
        v[x-1].append(y-1)
    for i in range(n):
        dfs(i)
    print(max(dp))

#H
def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])

#I
def J():
    n = I()
    p = list(map(float, input().split()))
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(n+1):
            dp[i+1][j] = p[i]*dp[i][j-1]+(1-p[i])*dp[i][j]

    ans = 0
    m = math.floor(n/2)
    for i in range(m+1,n+1):
        ans += dp[n][i]
    print(ans)

#J
def K():
    n = I()


#Solve
if __name__ == "__main__":
    G()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
def F():
    s = S()
    t = S()
    dp = [["" for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + s[i]
            else:
                if len(dp[i][j + 1]) < len(dp[i + 1][j]):
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    print(dp[len(s)][len(t)])
    return

#G
def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        #print(dp, i)
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                #print(dp, k , i)
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                #print(dp)
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return

#H
def H():
    return

#I
def I():
    return 
#J

#K

#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    G()

Submission status: Accepted

Solution code:
# coding: utf-8
from functools import lru_cache

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

@lru_cache(maxsize = None)
def f(v):
    if not arc[v]:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    arc[x - 1].append(y - 1)
print(max(f(v) for v in range(n)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
indegree=[0]*(n+1)
adj=[0]*(n+1)
for i in range(n+1):
	adj[i]=[]
for i in range(m):
	x,y=map(int,input().split())
	adj[x].append(y)
	indegree[y]+=1
stk=[]
for i in range(n+1):
	if indegree[i]==0 and len(adj[i])>0:
		stk.append(i)
path_length=[0]*(n+1)
while len(stk)>0:
	s=stk[-1]
	stk.pop()
	for i in range(len(adj[s])):
		indegree[adj[s][i]]-=1
		path_length[adj[s][i]]=max(path_length[adj[s][i]],path_length[s]+1)
		if indegree[adj[s][i]]==0:
			stk.append(adj[s][i])
print(max(path_length))

Submission status: Accepted

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

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)
#print(g)
mem = [-1]*n

def dfs(v):
  if mem[v] != -1:
    return mem[v]
  mem[v] = r = max(dfs(w) for w in g[v]) +1 if g[v] else 0
  return r
print(max(dfs(t) for t in range(n)))

Submission status: Accepted

Solution code:
import sys,bisect
input = sys.stdin.readline
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 len(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))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N,M = map(int,input().split())
    dp = [-1]*N
    ad = [deque() for _ in range(N)]
    num = [0]*N
    for _ in range(M):
        x,y = map(int,input().split())
        x -= 1; y -= 1
        ad[x].append(y)
        num[y] += 1

    L = []
    S = deque()

    for v in range(N):
        if num[v] == 0:
            S.append(v)
            dp[v] = 0

    while S:
        v = S.popleft()
        L.append(v)
        for _ in range(len(ad[v])):
            nv = ad[v].popleft()
            num[nv] -= 1
            if num[nv] == 0:
                S.append(nv)
                if dp[nv] < dp[v] + 1:
                    dp[nv] = dp[v] + 1

    ans = max(dp)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

N,M = map(int,input().split())
dp = [-1]*N
ad = [deque() for _ in range(N)]
num = [0]*N
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    ad[x].append(y)
    num[y] += 1

L = []
S = deque()

for v in range(N):
    if num[v] == 0:
        S.append(v)
        dp[v] = 0

while S:
    v = S.popleft()
    L.append(v)
    for _ in range(len(ad[v])):
        nv = ad[v].popleft()
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
            if dp[nv] < dp[v] + 1:
                dp[nv] = dp[v] + 1

ans = max(dp)
print(ans)

Submission status: Accepted

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

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

    dp = [-1]*N

    def rec(nodes):
        if dp[nodes] != -1:
            return dp[nodes]
        res = 0
        for ne in ad[nodes]:
            option = rec(ne)+1
            if res < option:
                res = option
        dp[nodes] = res
        return dp[nodes]

    ans = 0
    for i in range(N):
        res = rec(i)
        if ans < res:
            ans = res
    print(ans)
    
main()

Submission status: Accepted

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

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

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne in ad[nodes]:
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 11:58:20 2019
DP_G
@author: maezawa
"""
import sys
sys.setrecursionlimit(10**6)

memo = [-1] * (10**5+100)

def rec(nx):
    if memo[nx] > -1:
        return memo[nx]
    depth = 0
    for edge in edges[nx]:
        nrec = rec(edge) + 1
        if nrec > depth:
            depth = nrec
    memo[nx] = depth
    return depth

n, m = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(int, input().split()))
    edges[x-1].append(y-1)
    
maxdepth = 0
for node in range(n):
    depth = rec(node)
    if maxdepth < depth:
        maxdepth = depth
        
print(maxdepth)

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop()
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    for v in outs[sq]:
        last[v] = max(last[v], last[sq] + 1)

print(max(last))

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N

for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

last = [0] * N
while q != []:
    qn = q.pop()
    for v in outs[qn]:
        ins[v] -= 1
        last[v] = max(last[v], last[qn] + 1)
        if ins[v] == 0:
            q.append(v)

print(max(last))

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
inedge = [0] * N
edge = [ [] for _ in range(N) ]
for i in range(M):
    x,y = map(int,input().split(" "))
    inedge[y-1] += 1
    edge[x-1].append(y-1)

stack = []
for i in range(N):
    if inedge[i] == 0:
        stack.append((i,0))

ans = [0] * N
while len(stack) != 0:
    nextVer,passLen = stack.pop()
    for e in edge[nextVer]:
        inedge[e] -= 1
        ans[e] = max(ans[e],passLen+1)
        if inedge[e] == 0:
            stack.append((e,ans[e]))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
def topological_sort(G, Grev, N):
    Q = deque()
    T = [0]*(N+1)
    L = []
    for i in range(1, N+1):
        if len(Grev[i]) == 0:
            Q.append(i)
        T[i] = len(Grev[i])
    while Q:
        u = Q.pop()
        L.append(u)
        for v in G[u]:
            T[v] -= 1
            if T[v] == 0:
                Q.append(v)
    return L

def longest_path(L, G, Grev, N):
    longest = 0
    dist = [0]*(N+1)
    for u in L:
        for v in Grev[u]:
            dist[u] = max(dist[u], dist[v]+1)
            longest = max(longest, dist[u])
    return longest


N, M = [int(s) for s in input().split(" ")]
G = dict()
Grev = dict()
for i in range(1, N+1):
    G[i] = []
    Grev[i] = []
for _ in range(M):
    u, v = [int(s) for s in input().split(" ")]
    G[u].append(v)
    Grev[v].append(u)
L = topological_sort(G, Grev, N)
result = longest_path(L, G, Grev, N)
print("{}".format(result))

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

sys.setrecursionlimit(10**6)


def main():
    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
    for node, children in enumerate(graph):
        if children == []:
            dp[node] = 0

    def solve(x):
        for child in graph[x]:
            if dp[child] == -1:
                solve(child)

        dp[x] = 1 + max(dp[child] for child in graph[x])

    for i in range(n):
        if dp[i] == -1:
            solve(i)

    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)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


topological_order = topological_sort(G)
dp = [0] * N
for t in topological_order:
    for to in G[t]:
        dp[to] = max(dp[to], dp[t] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
import collections

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

L_minus = [[] for i in range(N)]
L_plus = [0 for i in range(N)]

dp = [0 for i in range(N)]

for i in range(M) :
    x,y = L[i]
    x -= 1
    y -= 1
    L_plus[y] += 1
    L_minus[x].append(y)

A = collections.deque()

for i in range(N) :
    if L_plus[i] == 0 :
        A.append(i)

while A :
    x = A.popleft()
    
    for y in L_minus[x] :
        L_plus[y] -= 1
        if L_plus[y] == 0 :
            A.append(y)
        dp[y] = max(dp[y], dp[x]+1)

ans = max(dp)

print(ans)

Submission status: Accepted

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

L_minus = [[] for i in range(N)]
L_plus = [0 for i in range(N)]

dp = [0 for i in range(N)]

for i in range(M) :
    x,y = L[i]
    x -= 1
    y -= 1
    L_plus[y] += 1
    L_minus[x].append(y)

A = []

for i in range(N) :
    if L_plus[i] == 0 :
        A.append(i)

while A :
    x = A.pop()
    
    for y in L_minus[x] :
        L_plus[y] -= 1
        if L_plus[y] == 0 :
            A.append(y)
        dp[y] = max(dp[y], dp[x]+1)

ans = max(dp)

print(ans)

Submission status: Accepted

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

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

v = [-1] * (n + 1)
x = [[] for _ in range(n + 1)]

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

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

    rt = 0
    for node in x[i]:
        tmp = dfs(node) + 1
        if rt < tmp:
            rt = tmp

    #メモ化再帰
    v[i] = rt
    return rt

ans = 0

for k in range(1,n+1):
    tmp2 = dfs(k)

    if tmp2 > ans:
        ans = tmp2

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import defaultdict, deque

INF = 10 ** 5
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()

G = defaultdict(list)
G2 = defaultdict
in_degree = [0] * n
for _ in range(m):
    x, y = LI_()
    G[x].append(y)
    in_degree[y] += 1

# トポロジカルソート
q = deque()
for v, e in enumerate(in_degree):
    if e == 0:
        q.append(v)

res = []
while q:
    v = q.popleft()
    res.append(v)
    for nv in G[v]:
        in_degree[nv] -= 1
        if in_degree[nv] == 0:
            q.append(nv)

dp = [0] * n
for v in res:
    for nv in G[v]:
        dp[nv] = max(dp[nv], dp[v] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque

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

E = [[] for i in range(n+1)]
IN = [0] * (n+1)

for a, b in X:
    E[a].append(b)
    IN[b] += 1

q = deque((i, 0) for i in range(1, n+1) if IN[i] == 0)
D = [0] * (n+1)

while q:
    i, d = q.popleft()
    IN[i] -= 1
    if IN[i] > 0:
        continue
    D[i] = d
    for e in E[i]:
        q.append((e, d+1))

print(max(D))

Submission status: Accepted

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

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

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

for a, b in X:
    E[a].append(b)

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

def dfs(i):
    if memo[i] != -1:
        return memo[i] + 1
    if not E[i]:
        return 0

    memo[i] = max(dfs(e) for e in E[i])
    return memo[i] + 1

print(max(dfs(i) for i in range(1, n+1)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
q=[]
for i in range(n):
    if not oya[i]:
        q.append([i,ko[i]])
while q:
    now,path=q.pop()
    for i in path:
        oya[i].remove(now)
        if not oya[i]:
            q.append([i,ko[i]])
        rank[i]=max(rank[i],rank[now]+1)
print(max(rank))