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
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)

dist = [-1]*n


def longest_path(v):
    if dist[v] != -1:
        return dist[v]
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    dist[v] = retval
    return dist[v]


ans = 0
for i in range(n):
    ans = max(ans, longest_path(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)


def memoize(f):
    memo = dict()

    def memoized(*args):
        if args in memo.keys():
            return memo[args]
        else:
            memo[args] = f(*args)
            return memo[args]
    return memoized

@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


ans = 0
for i in range(n):
    ans = max(ans, longest_path(i))
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for i in range(n)]
I = [0 for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    I[y-1] += 1
# Q:出発点の候補
Q = [i for i in range(n) if I[i] == 0]
# L[i]=iを終点とする最長パスの長さ
L = [0 for i in range(n)]
while Q:
    i = Q.pop()
    while G[i]:
        j = G[i].pop()
        I[j] -= 1
        L[j] = max(L[j], L[i]+1)
        if I[j] == 0:
            Q.append(j)
print(max(L))

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する


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

dp = [-1 for i in range(N)] #node[i]からの最長経路長を記す -1で未決定を示す

def memo(i):
    if dp[i] != -1:
        return dp[i]
    a=0
    for j in to[i]:
        a=max(a, memo(j)+1)
    dp[i] = a
    return a

lp = 0
for i in range(N):
    lp = max(lp,memo(i))
print(lp)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline

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

dp = [-1 for i in range(N)] #node[i]からの最長経路長を記す -1で未決定を示す

def memo(i):
    if dp[i] != -1:
        return dp[i]
    a=0
    for j in to[i]:
        a=max(a, memo(j)+1)
    dp[i] = a
    return a

lp = 0
for i in range(N):
    lp = max(lp,memo(i))
print(lp)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
gout = [[] for i in range(N)]
deg = [0] * N

for i in range(M):
    x, y = MAP()
    gout[x-1].append(y-1)
    deg[y-1] += 1
# only no_children 
topo = [v for v in range(N) if deg[v] == 0]
path_len = [0] * N
ans = 0
q = deque(topo)
# 子を持たない子スタート
while q:
    v = q.popleft()
    for t in gout[v]:
        # 親の子，vのカウントを減らす
        deg[t] -= 1
        # それでそれ以外の子がいなくなったら，
        # トポロジカルソートではスタックに積む
        if deg[t] == 0:
            q.append(t)
            path_len[t] = path_len[v] + 1
            ans = path_len[t]
print(ans)

Submission status: Accepted

Solution code:
#解説AC

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

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

dp=[-1]*n

def memo(v):
    if dp[v]+1: #更新済 dp[v]!=-1
        return dp[v]
    a=0
    for i in es[v]:
        a=max(a,memo(i)+1)
    dp[v]=a
    return a

ans=0
for i in range(n):
    ans=max(ans,memo(i))

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

def solve(g):
    dp = [-1]*len(g)
    def _solve(f):
        if dp[f] == -1:
            dp[f] = 0
            for c in g[f]:
                dp[f] = max(dp[f], 1 + _solve(c))
        return dp[f]
    for f in range(len(g)):
        _solve(f)
    # print(dp)
    return max(dp)

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    f, t = map(int, input().split())
    g[f-1].append(t-1)

print(solve(g))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

sys.setrecursionlimit(10**8)

#メモ化再帰
def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num

#入力受け取り
N, M = mi()
x = li2(M)

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

#メモ化再帰を実行
dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque

N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1

for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append([i,0])
queue = deque(topo[:])
while queue:
    n1,cnt = queue.popleft()
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append([n2,cnt+1])
            queue.append([n2,cnt+1])
print(max([v[1] for v in topo]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()

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

used = [False] * n
top = []


def dfs(i):
    if not used[i]:
        used[i] = True
        for j in e[i]:
            dfs(j)
        top.append(i)


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

ans = [0] * n
for i in reversed(top):
    for j in e[i]:
        ans[j] = max(ans[j], ans[i] + 1)
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
N, M = map(int, input().split())
d = [0]*N
G = defaultdict(list)
for i in range(M):
    s, t = map(int, input().split())
    d[t-1] += 1
    G[s-1].append(t-1)
q = deque([])
for i in range(N):
    if d[i] == 0:
        q.append(i)
ans = []
while q:
    s = q.popleft()
    ans.append(s)
    for t in G[s]:
        d[t] -= 1
        if d[t] == 0:
            q.append(t)
dp = [0] * (N+1)
num = 0
for i in range(0,N):
    for n in G[ans[i]]:
        dp[n] = max(dp[n], dp[ans[i]]+1)
print(dp[ans[-1]])

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

sys.setrecursionlimit(10**8)

#メモ化再帰
def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num

#入力受け取り
N, M = mi()
x = li2(M)

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

#メモ化再帰を実行
dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

sys.setrecursionlimit(10**9)

#メモ化再帰
def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num

#入力受け取り
N, M = mi()
x = li2(M)

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

#メモ化再帰を実行
dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

sys.setrecursionlimit(10**6)

def rec(x):
    global dp
    if dp[x]!=-1:
        return dp[x]
    num = 0
    for a in adj[x]:
        num = max(num, rec(a)+1)
    dp[x] = num
    return num


#入力受け取り
N, M = mi()
x = li2(M)

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

dp = [-1]*N
for i in range(N):
    rec(i)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
sys.setrecursionlimit(10**6)

N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x):
    if flag[x]:
        return None
    else:
        flag[x] = 1
        for a in adj[x]:
            dfs(a)
        global ans
        ans.appendleft(x)

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

dp = [0]*N
for a in ans:
    for b in adj[a]:
        dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from collections import deque
sys.setrecursionlimit(10**6)

N, M = mi()
x = li2(M)

adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])

flag = [0]*N
ans = deque([])

def dfs(x, ans):
    if flag[x]:
        return None
    else:
        flag[x] = 1
        if adj[x]:
            for a in adj[x]:
                dfs(a, ans)
        #global ans
        ans.appendleft(x)

for i in range(N):
    dfs(i, ans)

dp = [0]*N
for a in ans:
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[b], dp[a] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
N, M = mi()
x = li2(M)

#dp = dp2(0, 2, N)
dp = [[0, []] for i1 in range(N+1)]


for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    if dp[x[i][1]][1] != []:
        for a in dp[x[i][1]][1]:
            dp[a][0] = max(dp[x[i][1]][0] + 1, dp[a][0])

print(dp)
print(max([row[0] for row in dp])) 
'''
###トポロジカルソート
from collections import deque
N, M = mi()
x = li2(M)

h = [0]*N
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    h[x[i][1]] += 1
    adj[x[i][0]].append(x[i][1])

zeros = deque([])
#ans = []
for i in range(N):
    if h[i] == 0:
        zeros.append(i)
        #ans.append(i)

dp = [0]*N

while(zeros != deque()):
    a = zeros.popleft()
    if(adj[a]):
        for b in adj[a]:
            h[b] -= 1
            if h[b] == 0:
                zeros.append(b)
                dp[b] = max(dp[a] + 1, dp[b])
                #ans.append(b)
'''
dp = [0]*N
for a in ans:
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[a] + 1, dp[b])

print(dp[ans[-1]])
'''
print(max(dp))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
N, M = mi()
x = li2(M)

#dp = dp2(0, 2, N)
dp = [[0, []] for i1 in range(N+1)]


for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    if dp[x[i][1]][1] != []:
        for a in dp[x[i][1]][1]:
            dp[a][0] = max(dp[x[i][1]][0] + 1, dp[a][0])

print(dp)
print(max([row[0] for row in dp])) 
'''
from collections import deque
N, M = mi()
x = li2(M)

h = [0]*N
adj = [[] for i in range(N)]
for i in range(M):
    x[i][0] -= 1
    x[i][1] -= 1
    h[x[i][1]] += 1
    adj[x[i][0]].append(x[i][1])

zeros = deque([])
ans = []
for i in range(N):
    if h[i] == 0:
        zeros.append(i)
        ans.append(i)

while(zeros != deque()):
    a = zeros.popleft()
    if(adj[a]):
        for b in adj[a]:
            h[b] -= 1
            if h[b] == 0:
                zeros.append(b)
                ans.append(b)

#print(ans)

dp = [0]*N
#print(ans)
#print(adj)
for a in ans:
    #print(dp)
    if adj[a]:
        for b in adj[a]:
            dp[b] = max(dp[a] + 1, dp[b])
#print(dp)
print(dp[ans[-1]])

Submission status: Accepted

Solution code:

import sys

# 再起回数上限変更
sys.setrecursionlimit(1000000)

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


class Graph(object):
    def __init__(self, n: int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def add_edge(self, v1: int, v2: int, undirected=False):
        self.adjacency_dict[v1].append(v2)
        if undirected:
            self.adjacency_dict[v2].append(v1)


def find_longest(v):
    """ vからの有向最長パスをの長さをdp[v]とする """
    global dp
    if dp[v] > 0:
        return dp[v]

    res = 0
    for nv in g.adjacency_dict[v]:
        res = max(res, find_longest(nv) + 1)

    dp[v] = res
    return res


g = Graph(N)
for i in range(M):
    x, y = map(int, input().split())
    g.add_edge(x - 1, y - 1)
# print(g.adjacency_dict)

dp = [-1] * N
# gにおいて出次数が0のところのdpを0とする
for v in range(N):
    if len(g.adjacency_dict[v]) == 0:
        dp[v] = 0
# print(dp)

for v in range(N):
    find_longest(v)

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)]

# xは始点、yは次点
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    g[x].append(y)
    
dp = [-1]*n
 
def solve(i): # 始点iから行ける場所を探索
    # すでに計算されているなら、後の距離は計算できている
    if dp[i] != -1:
        return dp[i]
    # 初期は長さ0
    tmp = 0
    # 始点iから次点にDFS
    for j in g[i]:
        #今までの距離と比較
        tmp = max(tmp, solve(j) + 1)
    # dp[i]はiからスタートして最長距離が記録される
    # 空のリスト（もう次点が存在しない）にたどり着いたらDFS終わり
    dp[i] = tmp
    return tmp
 
for i in range(n):
    solve(i)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

dp = [-1 for _ in range(N+1)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    
    paths = 0
    for t in links[i]:
        paths = max(paths, search(t)+1)
    
    dp[i] = paths
    return paths

for i in range(1, N+1):
    search(i)

print(max(dp))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)


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

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

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

memo = [-1]*N

def DFS(v):
    if memo[v]!=-1:
        return memo[v]
    if len(e_list[v])==0:
        memo[v] = 0
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    memo[v] = res
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
import sys
sys.setrecursionlimit(10**7)

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ---
N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

Submission status: Accepted

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

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

dp=[-1]*N #各ノードを始点とした時の最長経路

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
G = dict([[i, []] for i in range(N)])
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)

dp = [-1] * N


def rec(v):
    if dp[v] >= 0:
        return dp[v]
    if len(G[v]) == 0:
        return 0

    ret = -1
    for nv in G[v]:
        ret = max(ret, rec(nv) + 1)

    dp[v] = ret
    return ret


print(max([rec(v) for v in range(N)]))

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x,y = map(int,input().split())
        edge[x-1].append(y-1)
        
    dist = [-1 for _ in range(N)]
            
    def dfs(s):
        if dist[s] != -1:
            return dist[s]
        else:
            ret = 0
            for fol in edge[s]:
                ret = max(ret,dfs(fol)+1)
            dist[s] = ret
            return ret

    for i in range(N):
        dfs(i)
        
    print(max(dist))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
M = mod = 10**9 +7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]


def dfs(root):
    global ans,g
    if ans[root]:return 

    temp = 0
    for j in g[root]:dfs(j)
    if len(g[root]):temp = max(ans[j] for j in g[root])
    ans[root] = 1 + temp

n,m = li()
g = defaultdict(set)
for i in range(m):
    a,b = li()
    g[a].add(b)

ans = [0]*(n + 1)

for j in range(1,n + 1):
    if not ans[j]:dfs(j)

print(max(ans) - 1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, M = MAP()

gout = [[] for _ in range(N)]
deg = [0]*N
for _ in range(M):
	x, y = MAP()
	gout[x-1].append(y-1)
	deg[y-1] += 1
topo = [v for v in range(N) if deg[v]==0]
path_len = [0]*N
deq = deque(topo)
ans = 0
while deq:
    v = deq.popleft()
    for t in gout[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            path_len[t] = path_len[v] + 1
            ans = path_len[t]

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
parents = [[] for _ in range(n)]
outdegree = [0] * n
indegree = [0] * n
path_root = [0] * n
for _ in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  parents[y].append(x)
  outdegree[x] += 1
  indegree[y] += 1
stack = [i for i in range(n) if outdegree[i] == 0]
while stack:
  vertex = stack.pop()
  path_length = path_root[vertex] + 1
  for parent in parents[vertex]:
    outdegree[parent] -= 1
    indegree[vertex] -= 1
    path_root[parent] = max(path_root[parent], path_length)
    if outdegree[parent] == 0:
      stack.append(parent)
print(max(path_root))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
ro = [True for _ in range(n)]
dp = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
	ro[y-1] = False

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return

for j in range(n):
	if ro[j] == True:
		search(j)

print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
in_path = defaultdict(lambda: [])
out_path = defaultdict(lambda: [])

for m in range(M):
    x, y = map(int, input().split())
    in_path[y].append(x)
    out_path[x].append(y)

check = [False]*(N+1)
memo = [0]*(N+1)


def dp(i):
    if check[i]:
        return memo[i]
    else:
        check[i] = True
        if not out_path[i]:
            return 0
        else:
            max_path = 0
            for node in out_path[i]:
                max_path = max(dp(node), max_path)
            max_path += 1
            memo[i] = max_path
            return max_path


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

print(ans)

Submission status: Accepted

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

n,m = map(int,input().split())
e = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
def dfs(x):
    num = 0
    for nex in e[x]:
        if dis[nex] < 0:
            dfs(nex)
        num = max(num,dis[nex]+1)
    dis[x] = num
    return 
dis = [-1]*n
for i in range(n):
    if dis[i] < 0:
        dfs(i)
print(max(dis))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,m = map(int,input().split())
e = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
def dfs(x):
    num = 0
    for nex in e[x]:
        if dis[nex] < 0:
            dfs(nex)
        num = max(num,dis[nex]+1)
    dis[x] = num
    return 
dis = [-1]*n
for i in range(n):
    if e[i] and dis[i] < 0 :
        dfs(i)
print(max(dis))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n,m = map(int,input().split())
e = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
dis = [0]*n

def dfs(x):
    num = 0
    for nex in e[x]:
        if dis[nex] < 0:
            dfs(nex)
        num = max(num,dis[nex]+1)
    dis[x] = num
    return 
dis = [-1]*n
for i in range(n):
    if e[i] and dis[i] < 0 :
        dfs(i)
print(max(dis))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

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

not_start_point = set()
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    not_start_point.add(y)
    to_point[x].append(y)

start_point = set(range(N)) - not_start_point

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

ans = 0
for s in start_point:
    ans = max(ans, dp(s))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

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

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

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

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

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

print(max(dp_memo))

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
to = [0]*n
dp = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    path[x-1].add(y-1)
    to[y-1] += 1

que = deque()
for i in range(n):
    if to[i] == 0:
        que.append(i)
ans = 0
while que:
    p = que.popleft()
    for i in path[p]:
        to[i] -= 1
        if to[i] == 0:
            que.append(i)
        dp[i] = max(dp[i], dp[p] + 1)
        ans = max(ans, dp[i])
print(ans)