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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G_fix
# CreatedDate:  2020-06-05 21:28:41 +0900
# LastModified: 2020-06-05 22:05:41 +0900
#


import os
import sys
from collections import deque
#import numpy as np
#import pandas as pd


def main():
    n,m = map(int,input().split())
    path = [[] for _ in range(n+1)]
    to_cnt = [0]*(n+1)
    longest_cnt = [0]*(n+1)
    for _ in range(m):
        x,y = map(int,input().split())
        path[x].append(y)
        to_cnt[y]+=1
    
    Q = deque()
    for i in range(1,n+1):
        if to_cnt[i]==0:
            Q.append(i)

#    longest_cnt[s]=1

    while(Q):
        u = Q.popleft()
        for v in path[u]:
            to_cnt[v]-=1
            if longest_cnt[u]+1>longest_cnt[v]:
                longest_cnt[v]=longest_cnt[u]+1
            if to_cnt[v]==0:
                Q.append(v)
    print(max(longest_cnt))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = [-1 for _ in range(N)]

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

#solve DAG and topological sort by memo recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    dp[v] = ret
    return ret
for v in range(N):
    dp[v] = f(v)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())

sys.setrecursionlimit(10**9)

vertices = [[] for i in range(N+1)]
dp = [-1] * (N+1)

for _ in range(M):
    fro, to = map(int, input().split())
    vertices[fro].append(to)

def dfs(i):
    
    if dp[i] != -1:
        return dp[i]
    
    temp = 0
    for vertex in vertices[i]:
        temp = max(temp, dfs(vertex)+1)
        
    dp[i] = temp
    return temp

for i in range(1,N+1):
    dfs(i)
    
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+1)]

dp = [-1] * (n+1)
for _ in range(m):
    v1 , v2 = map(int,input().split())
    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(1,n+1):
    res = max(res, dfs(i))
print(res)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
graph=[[]for _ in range(N)]
deg=[0]*N
for i in range(M):
    xx,yy=map(int,input().split())
    graph[xx-1].append(yy-1)
    deg[yy-1]+=1

que=[]
dp=[0]*N

for i in range(N):
    if deg[i]==0:
        que.append(i)
while len(que)>0:
    k=que.pop(0)
    for x in graph[k]:
        deg[x]-=1
        if deg[x]==0:
            que.append(x)
            dp[x]=max(dp[x],dp[k]+1)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(100000)


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(M):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        y -= 1
        adj_nodes[x].append(y)
    dp = [-1 for _ in range(N)]

    def rec(v):
        if dp[v] >= 0:
            return dp[v]
        ret = 0
        for nv in adj_nodes[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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n,m=reads()
link=[[]for i in range(n)]
for i in range(m):
  x,y=reads()
  link[x-1].append(y-1)
#print(link)
@lru_cache(None)
def dp(k):
  res=0
  for ele in link[k]:
    res=max(res,dp(ele)+1)
  return res
res=1
for i in range(n)  :
  res=max(res,dp(i))
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def dfs(a,adjl,visited,dp):
  for i in adjl[a]:
    if visited[i]==0:
      visited[i]=1
      dfs(i,adjl,visited,dp)
 
    dp[a]=max(dp[a],1+dp[i])
n,m=map(int,input().split())
li=[]
for i in range(m):
  li.append([int(k) for k in input().split()])
adjl=[[] for j in range(n+1)]
for k in range(len(li)):
  adjl[li[k][0]].append(li[k][1])
visited=[0]*(n+1)
dp=[0]*(n+1)
for a in range(1,n+1):
  if visited[a]==0:
    visited[a]=1
    dfs(a,adjl,visited,dp)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def f(x):
	global hashi
	if(x in hashi):
		return hashi[x]
	if(adj[x]==[]):
		return 0
	mino=0
	for i in adj[x]:
		mino=max(mino,f(i))
	hashi[x]=mino+1
	return mino+1
l=input().split()
n=int(l[0])
m=int(l[1])
adj=[[] for i in range(n+1)]
for i in range(m):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	adj[u].append(v)
maxa=0
hashi=dict()
for i in range(1,n+1):
	maxa=max(maxa,f(i))
print(maxa)

Submission status: Accepted

Solution code:
def addEdge(adj, u, v):
    adj[u].append(v)
def dfs(node,dp,vis,adj):
    vis[node] = True 
    for i in range(len(adj[node])):
        if not vis[adj[node][i]]: 
            dfs(adj[node][i], dp,vis,adj)
        dp[node] = max(dp[node], 1 + dp[adj[node][i]])
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())
adj = [[] for i in range(n + 1)] 
for i in range(m):
    u,v=map(int, input().split())
    addEdge(adj,u,v)
dp=[0]*(n+1)
vis=[False]*(n+1)
for i in range(1,n+1):
    if not vis[i]:
        dfs(i,dp,vis,adj)
ans=0
for i in range(1, n + 1):   
    ans = max(ans, dp[i])  
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    out_degree = [0]*N
    max_path = [0]*N
    G = defaultdict(list)
    for _ in range(M):
        x, y = read_ints()
        x -= 1
        y -= 1
        out_degree[x] += 1
        G[y].append(x)
    Q = [i for i, degree in enumerate(out_degree) if degree == 0]
    while len(Q):
        node = Q.pop()
        while len(G[node]):
            parent = G[node].pop()
            out_degree[parent] -= 1
            max_path[parent] = max(max_path[parent], max_path[node]+1)
            if out_degree[parent] == 0:
                Q.append(parent)
    return max(max_path)


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] += 1
    d = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while d:
        i = d.popleft()
        for j in li[i]:
            deg[j] -= 1
            if deg[j] == 0:
                dp[j] = max(dp[j] ,dp[i] + 1)
                d.append(j)
    print(max(dp))
a()

Submission status: Accepted

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

N,M = map(int,input().split())
XY = [[] for i in range(N + 1)]

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

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

  
def recur(n):
  if path[n] != -1:
    return path[n]
  
  elif XY[n] == []:
    path[n] = 0
    return path[n]
        
  else:
    ret = 0
    for chi in XY[n]:
      ret = max(ret,recur(chi) + 1)
    
    path[n] = ret
    return path[n]
    
for i in range(N):
  recur(i)

print(max(path))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

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

# DAG TopoSort
in_count = [0]*N
edge = [[] for _ in range(N)]
for u,v in xy:
    in_count[v-1] += 1
    edge[u-1].append(v-1)

S = []
L = [] #Sort結果
index = [0]*N # 頂点vのLにおけるインデックスindex[v]
for i in range(N):
    if in_count[i]==0: S.append(i)
while S:
    v = S.pop()
    index[v] = len(L)
    L.append(v)
    for nv in edge[v]:
        in_count[nv] -= 1
        if in_count[nv]==0:
            S.append(nv)

dp = [0] * N
for i,v in enumerate(L):
    for nv in edge[v]:
        dp[index[nv]] = max(dp[index[nv]], dp[i]+1)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    # 各頂点の次数
    deg = [0 for _ in range(n)]
    # グラフ
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        deg[b - 1] += 1

    # 入力辺を持たないノードの集合
    que = deque([])
    for i in range(n):
        if deg[i] == 0:
            que.append(i)

    # トポロジカルソートを行いながら、入力辺を持たないノードからの最長経路を求める
    dp = [0 for _ in range(n)]
    while que:
        v = que.popleft()
        for nv in edge[v]:
            # 入力辺を一つ消す
            deg[nv] -= 1
            if deg[nv] == 0:
                que.append(nv)
                dp[nv] = max(dp[nv], dp[v] + 1)

    print(max(dp))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    # 各頂点の次数
    deg = [0 for _ in range(n)]
    # グラフ
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        deg[b - 1] += 1

    que = deque([])
    for i in range(n):
        if deg[i] == 0:
            que.append(i)

    dp = [0 for _ in range(n)]
    while que:
        v = que.popleft()
        for nv in edge[v]:
            deg[nv] -= 1
            if deg[nv] == 0:
                que.append(nv)
                dp[nv] = max(dp[nv], dp[v] + 1)

    res = 0
    for j in range(n):
        res = max(res, dp[j])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#for _ in range(int(input())):
#	n=int(input())
#	n,m=map(int,input().split())
#	s=input().strip()
sys.setrecursionlimit(10**9)
def dfs(i):
	if dp[i]!=-1:return dp[i]
	c=0
	for j in v[i]:c=max(c,dfs(j)+1)
	dp[i]=c
	return c

n,m=map(int,input().split())
v=[[] for i in range(n+1)]
for i in range(m):
	x,y=map(int,input().split())
	v[x].append(y)
dp = [-1]*(n+1) 
m=0
for i in range(1,n+1):
	m=max(m,dfs(i))
print(m)

Submission status: Accepted

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

def dfs(x): #グラフでの再帰DFS
    if dp[x] != -1:
        return dp[x] #すでに値が決まっていたらそれをかえす
    ans = 0
    for e in graph[x]: #すべての枝について
        ans = max(ans,1 + dfs(e))
    dp[x] = ans
    return ans # 最も長い距離を返す　

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

graph = [[] for i in range(n+1)]
dp = [-1]
for i in range(1,n+1):
    dp.append(-1) # dpは初期値-1

for _ in range(m): # グラフの作成
    a,b = map(int, input().split())
    graph[a].append(b)
    #graph[b].append(a) #無向グラフの時
    
ans=0

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

Submission status: Accepted

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

def f(x):#dpは
    if dp[x]!=-1:
        return dp[x]#すでに値が決まっていたらそれをかえす
    ans=0
    for e in d[x]:#すべての枝について
        ans=max(ans,1+f(e))
    dp[x]=ans
    return ans

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

d={}
dp=[-1]
for i in range(1,n+1):
    d[i]=[]#dは初期値を[]
    dp.append(-1)#dpは初期値-1

for _ in range(m):
    a,b = map(int, input().split())
    d[a].append(b)#有向グラフをdictで
    
ans=0
for i in range(1,n+1):
    ans=max(ans,f(i))
print(ans)

Submission status: Accepted

Solution code:
from _collections import defaultdict
import sys
import collections
import sys
sys.setrecursionlimit(10**6)


def get_ls():
    return list(map(int, input().split()))


def longest_path_util(node, graph, dp):

    res = 0

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

    for neib in graph[node]:
        res = max(res, longest_path_util(neib, graph, dp) + 1)

    dp[node] = res

    return dp[node]


graph = defaultdict(list)

[n, k] = get_ls()

dp = [-1] * n

for _ in range(k):
    [x, y] = get_ls()
    graph[x - 1].append(y - 1)

ans = 0

for i in range(n):
    ans = max(ans, longest_path_util(i, graph, dp))

print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

dp=[-1]*100100
G=[[] for _ in range(100100)]

def dfs(v):
  if dp[v]!=-1:
    return dp[v]
  dp[v]=r=max(dfs(w) for w in G[v])+ 1 if G[v] else 0
  return r

def main():
  n,k=LI()

  for _ in range(k):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)

  return max(dfs(v) for v in range(n))

# main()
print(main())

Submission status: Accepted

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

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]
#Topological sort Gは辞書として渡す
def tsort(N,G,dic):
    res = 0
    #Topological Sort
    if dic[N] != -1:
        return dic[N]
    for node in G[N]:
        res = max(res,tsort(node,G,dic)+1)
    dic[N] = res
    return dic[N]

[n,m] = getlsi()
dic_next = collections.defaultdict(list)
dp = [-1] * n
for i in range(m):
    [x,y] = getlsi()
    dic_next[x-1].append(y-1)
ans = 0
for i in range(n):
    ans = max(ans,tsort(i,dic_next,dp))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N,M = map(int,input().split())
lst=[{} for f in range(N)]
for i in range(M):
 x,y=map(int,input().split())
 lst[x-1][y-1]=1
memo = {}
def cost(a):
 ans=0
 if a in memo:
  return memo[a]
 else:
  for i in lst[a]: 
   if i in memo:
    ans=max(memo[i]+1,ans)
   else:
    ans=max(cost(i)+1,ans)
  memo[a]=ans
  return ans
T=0
for i in range(N):
 T=max(T,cost(i))
print(T)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N,M = map(int,input().split())
lst=[{} for f in range(N)]
for i in range(M):
 x,y=map(int,input().split())
 lst[x-1][y-1]=1
memo = {}
def cost(a):
 ans=0
 for i in lst[a]: 
  if i in memo:
    ans=max(memo[i]+1,ans)
  else:
    ans=max(cost(i)+1,ans)
 memo[a]=ans
 return ans
T=0
for i in range(N):
 T=max(T,cost(i))
print(T)

Submission status: Accepted

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


def dfs(v):
    global dp
    if dp[v] != -1:
        return dp[v]
    res = 0
    for next_v in e[v]:
        res = max(dfs(next_v) + 1, res)
    dp[v] = res
    return res


def main():
    N, M = map(int, input().split())
    global e
    e = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
    global dp
    dp = [-1]*N
    ans = -1
    for v in range(N):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    input_edges = [0]*N
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        input_edges[v] += 1
    queue = deque()
    dp = [-1] * N
    for i, input_edge in enumerate(input_edges):
        if input_edge == 0:
            queue.appendleft(i)
            dp[i] = 0
    topological_sorted = []
    while queue:
        v = queue.pop()
        topological_sorted.append(v)
        for other_side in e[v]:
            input_edges[other_side] -= 1
            if input_edges[other_side] == 0:
                queue.appendleft(other_side)
    for v in topological_sorted:
        for other_side in e[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
MEMO = [-1 for _ in range(N+1)]

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


def dp_LP(v):# 頂点nから始まる最長経路を返す.
  if MEMO[v] != -1:
    return MEMO[v]
  else:
    ans = 0
    for i in G[v]:
      ans = max(ans, dp_LP(i)+1)
    MEMO[v] = ans

    return ans



answer = 0
for n in range(1,N+1):
  answer = max(answer, dp_LP(n))
print(answer)

Submission status: Accepted

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

def f(x):
    if dp[x]!=-1:
        return dp[x]
    ans=0
    for e in d[x]:
        ans=max(ans,1+f(e))
    dp[x]=ans
    return ans

n,m = list(map(int, input().split()))
d={}
dp=[-1]
for i in range(1,n+1):
    d[i]=[]
    dp.append(-1)
for _ in range(m):
    a,b = list(map(int, input().split()))
    d[a].append(b)
ans=0
for i in range(1,n+1):
    ans=max(ans,f(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): 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)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,M = MI()
to = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = MI()
    to[x].append(y)
dp = [-1]*(N+1)
def rec(i):
    if dp[i] != -1:
        return dp[i]
    ret = 0
    if to[i]:
        for v in to[i]:
            ret = max(ret,rec(v)+1)
    dp[i] = ret
    return ret

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(10000)

def main():
	n, m = rli()
	G = [[] for i in range(n+1)]
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
	ans = 0
	memo = [-1 for _ in range(n+1)]

	def longest(v):
		if memo[v] > -1:
			return memo[v]
		pathlen = 0
		for nbhr in G[v]:
			pathlen = max(pathlen, 1 + longest(nbhr))
		memo[v] = pathlen
		return pathlen

	for i in range(1, n+1):
		ans = max(ans, longest(i))

	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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

N, M = map(int, input().split())
ins = [0]*N
outs = defaultdict(list)

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

q = deque([v for v in range(N) if ins[v]==0])
dp = [0]*N

while q:
    v = q.popleft()
    
    for nv in outs[v]:
        dp[nv] = max(dp[nv], dp[v]+1)
        ins[nv] -= 1
        
        if ins[nv]==0:
            q.append(nv)

print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

n, m = map(int, input().split())
xy = []
node = defaultdict(int)
branch = defaultdict(list)
dp = [0]*(n+1) 

for _ in range(m):
    x, y = map(int, input().split())
    xy.append([x, y])
    node[y] += 1 #入り込むノードの数
    branch[x].append(y) # 枝分かれ先


res = []
queue = deque([i for i in range(1, n+1) if node[i]==0])
while queue:
    v = queue.popleft()
    res.append(v)
    
    for u in branch[v]:
        dp[u] = max(dp[u], dp[v]+1)
        node[u] -= 1
        if node[u] == 0:
            queue.append(u)



print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
adj=[]
dp=[0 for i in range(0,n+1)]
def dfs(i,p,adj,dp):
    # print(i)
    # print(i,p)
    if dp[i]!=0:
        return dp[i]
    for j in (adj[i]):
        if j==p:
            continue 
        else:
            dfs(j,i,adj,dp)
            dp[i]=max(dp[i],1+dp[j])
    return dp[i]
    
for i in range(n+1):
    adj.append([])
for _ in range(m):
    u,v=map(int,input().split())
    adj[u].append(v)

for i in range(1,n+1):
    if dp[i]==0:
        dfs(i,i,adj,dp)
# print(dp)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
adj=defaultdict(list)
deg=[0]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    adj[x].append(y)
    deg[y]+=1

dist=[0]*(n+1)

que=[]
for i in range(1,n+1):
    if deg[i]==0:
        que.append(i)

while que:
    v=que.pop()
    for i in adj[v]:
        deg[i]-=1
        if deg[i]==0:
            que.append(i)
        dist[i]=max(dist[i],dist[v]+1)

print(max(dist))

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w=1):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

edgenum=[0]*(n+1)
edge=[[] for i in range(n+1)]

for i in range(m):
    x,y=xy[i]
    edgenum[x]+=1
    edge[y].append(x)
# print(edgenum)
# print(edge)

d=deque()
itta=[0]*(n+1)
for i in range(n):
    i+=1
    if edgenum[i]==0:
        d.append(i)
# print(d)

while d:
    now=d.popleft()
    # print(itta,now)
    # print(edgenum)

    for i in edge[now]:
        edgenum[i]-=1
        if edgenum[i]==0:
            d.append(i)
            itta[i]=max(itta[i],itta[now]+1)
# print(itta)
print(max(itta))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    graph=[[]for _ in range(n)]
    deg=[0]*n #頂点iの入次数
    for x,y in XY:
        graph[x-1].append(y-1)
        deg[y-1]+=1
    que=deque()
    for v in range(n):
        if deg[v]==0:
            que.append(v)
    dp=[0]*n
    while que:
        v=que.popleft()
        for nv in graph[v]:
            deg[nv]-=1
            if deg[nv]==0:
                que.append(nv)
                dp[nv]=max(dp[nv],dp[v]+1)
    ans=0
    for v in range(n):
        ans=max(ans,dp[v])
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#G
N,M=map(int,input().split())
A=[[] for i in range(N+1)]
B=[0 for i in range(N+1)]
dp=[0 for j in range(N+1)]

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

st=[]
for i in range(1,N+1):
    if B[i]==0:
        st.append(i)
        dp[i]

while len(st):
    x=st.pop()
    for y in A[x]:
        dp[y]=max(dp[y],dp[x]+1)
        B[y]-=1
        if B[y]==0:
            st.append(y)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
memo=dict()
def rec(v):
    if v in memo:return memo[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    memo[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
def rec(v):
    if dp[v]!=-1:return dp[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    dp[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache
sys.setrecursionlimit(10**6)
@lru_cache(maxsize=None)
def rec(v):
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
def rec(v):
    if dp[v]!=-1:return dp[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    dp[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n,m=map(int,input().split(' '))
paths=defaultdict(list)
ins=[0]*(n+1)
for _ in range(m):
    x,y=map(int,input().split(' '))
    paths[x].append(y)
    ins[y]+=1

no_in=[y for y in range(1,n+1) if ins[y]==0]
depth=[0]*(n+1)
while no_in:
    x=no_in.pop()
    for y in paths[x]:
        ins[y]-=1
        depth[y]=max(depth[y],depth[x]+1)
        if ins[y]==0:
            no_in.append(y)

print(max(depth))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def dfs(u):
    if(dp[u]!=-1):
        return dp[u]
    for i in d[u]:
        if(dp[i]!=-1):
            dp[u]=max(dp[u],dp[i]+1)
        else:
            dp[u]=max(dp[u],dfs(i)+1)
    return max(dp[u],0)
from collections import defaultdict as dd
n,m=map(int,input().split())
d=dd(list)
for i in range(m):
    u,v=map(int,input().split())
    d[u].append(v)
dp=dd(lambda: -1)
mx=0
for i in range(1,n+1):
    if(dp[i]==-1):
        dp[i]=dfs(i)
    mx=max(mx,dp[i])
print(mx)