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:
from collections import deque

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Num = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    Num[y] += 1
Q = deque()
for i, n in enumerate(Num):
    if n == 0:
        Q.append(i)

DP = [0] * N
ans = 0
while Q:
    now = Q.pop()
    for nex in Edge[now]:
        DP[nex] = max(DP[nex], DP[now] + 1)
        Num[nex] -= 1
        if not Num[nex]:
            Q.append(nex)
print(max(DP))

Submission status: Accepted

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

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

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

def dfs(pos):
    if not edges[pos]:
        dp[pos] = 0
        return
    for n_pos in edges[pos]:
        if not used[n_pos]:
            dfs(n_pos)
        used[n_pos] = 1
        dp[pos] = max(dp[pos],dp[n_pos]+1)

    
for i in range(N):
    if used[i]:
        continue
    used[i] = True
    dfs(i)

print(max(dp))

Submission status: Accepted

Solution code:
n, m = map(int, input().strip().split())
graph = {i:[] for i in range(1, n+1)}

deg = [0 for i in range(n+1)]
for i in range(m):
    v1, v2 = map(int, input().strip().split())
    graph[v1].append(v2)
    deg[v2] += 1

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

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

while len(Q):
    curr = Q.pop()
    for i in graph[curr]:
        dp[i] = max(dp[i], dp[curr]+1)
        deg[i] -= 1
        if deg[i] == 0:
            Q.append(i)

print(max(dp))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

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

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



def saiki(num):
    if visited[num]==1:
        return dp[num]
    
    visited[num]=1
    value=0
    if linked[num]:
        for item in linked[num]:
            value=max(value,saiki(item)+1)
    dp[num]=value
    return value

dp=[0]*N
visited=[0]*N
ans=0
for i in range(N):
    ans=max(ans,saiki(i))

print(ans)

Submission status: Accepted

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

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

G=[[] for i in range(N)] #グラフを隣接リストで表現
for j in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)

dp=[-1]*N

def longest_path(v): #vを始点とした時の最長パスの長さ
    if dp[v] != -1: #更新済みの場合
        return dp[v]
    
    #更新されていなかった場合
    tmp_max = 0
    for u in G[v]:
        tmp_max = max(tmp_max,longest_path(u)+1)
    dp[v] = tmp_max #きちんとメモする
    
    return dp[v]

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def read_pair():
    return map(int, input().strip().split())

# Read graph
N, M = read_pair()
adj = [[] for x in range(N)]
rev = [[] for y in range(N)]

outdegree = [0] * N
for i in range(M):
    x, y = read_pair()

    # Use 0-indexed labels
    x -= 1
    y -= 1

    adj[x].append(y)
    rev[y].append(x)
    outdegree[x] += 1

maxpath = [0] * N
q = deque()

for x in range(N):
    if outdegree[x] == 0:
        q.append(x)

while q:
    x = q.popleft()
    for y in adj[x]:
        maxpath[x] = max(maxpath[x], 1 + maxpath[y])
    for z in rev[x]:
        outdegree[z] -= 1
        if outdegree[z] == 0:
            q.append(z)

print(max(maxpath))

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        graph[x].append(y)
    dp = [-1 for _ in range(n)]
    # dp[i] := iから距離が最も長い頂点への距離

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

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

q = deque(v for v in range(N) if V[v] == 0)

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

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        edges[y - 1].append(x - 1)
    used = [False for _ in range(n)]
    dp = [0 for _ in range(n)]
    
    def dfs(pos):
        if not edges[pos]:
            dp[pos] = 0
            return
        for n_pos in edges[pos]:
            if not used[n_pos]:
                dfs(n_pos)
            used[n_pos] = True
            dp[pos] = max(dp[pos], dp[n_pos] + 1)
            
    
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        dfs(i)
        
    print(max(dp))

main()

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
def f(i, e, dp):
    if dp[i] is not None:
        return dp[i]
    val = 0
    for nxt in e[i]:
        val = max(val, f(nxt, e, dp) + 1)
    dp[i] = val
    return dp[i]


def edu_dp_g_longest_path():
    n, m = map(int, input().split())
    e = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        e[x - 1].append(y - 1)
    dp = [None] * n
    result = 0
    for i in range(n):
        result = max(result, f(i, e, dp))
    print(result)

edu_dp_g_longest_path()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(110000) #再帰上限はデフォルトで1000回までなので，増やす。

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

graph = [[] for _ in range(110000)]

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

    graph[x].append(y)

dp_memo = [-1] * 110000

def dp(v):
    if dp_memo[v] != -1:
        return dp_memo[v]

    ret = 0
    for item in graph[v]:
        ret = max(ret, dp(item) + 1)

    dp_memo[v] = ret
    return ret

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

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

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

Submission status: Accepted

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

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

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

ans = 0
for i in range(N):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import sys
sys.setrecursionlimit(10**6)

def dfs(u):
    global grpah,vis,dp
    vis[u] = 1
    for i in graph[u]:
        if not vis[i]:
            dfs(i)
        dp[u] = max(dp[u],dp[i] + 1)

n,m = ip()
graph = [[] for i in range(n+1)]
for i in range(m):
    a,b = ip()
    graph[a].append(b)

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

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import sys
sys.setrecursionlimit(10**6)

def dfs(u):
    global grpah,vis,dp
    vis[u] = 1
    for i in graph[u]:
        if not vis[i]:
            dfs(i)
        dp[u] = max(dp[u],dp[i] + 1)

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)

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

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import sys
sys.setrecursionlimit(10**6)

def dfs(u):
    global grpah,vis,dp
    vis.add(u)
    for i in graph[u]:
        if i not in vis:
            dfs(i)
        dp[u] = max(dp[u],dp[i] + 1)

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
dp = [0]*(n+1)

vis = set()
for i in range(1,n+1):
    if i not in vis:
        dfs(i)
#print(dp)
print(max(dp))

Submission status: Accepted

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

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

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

ans = 0
for i in range(N):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M = list(map(int, input().split()))
P = [set() for _ in range(N)]
for i in range(M):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    P[x].add(y)

dp = [-1]*N


def lpth(n):
    if dp[n] > -1:
        return dp[n]
    l = P[n]
    # print(l)
    if l:
        s = [lpth(k) for k in l]
        # print(s)
        a = max(s)+1
    else:
        a = 0
    dp[n] = a
    return a


for i in range(N):
    dp[i] = lpth(i)
print(max(dp))
# print(dp)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

def topological_sort(adj, indeg):
    """
    幅優先探索によるトポロジカルソート
    O(|V|+|E|)

    adj: 隣接リスト
    indeg: 各ノード入次数を管理するリスト

    ret: トポロジカルソートされたリスト
    """
    is_visited = [0]*(N+1)
    ret = []

    def bfs(s):
        """
        sからBFSする
        """
        queue = deque([s])
        is_visited[s] = 1
        while queue:
            u = queue.popleft()
            # queueには入次数0のノードが入っているのでretに追加
            ret.append(u)

            for v in adj[u]: # uの子ノードを探索
                indeg[v] -= 1 #探索したら子の次数を減らす
                if (indeg[v] == 0) and (not is_visited[v]):
                    # 入次数0かつ未訪問なら
                    queue.append(v)
                    is_visited[v] = 1
    
    for u in range(1, N+1):
        if (indeg[u]==0) and (not is_visited[u]):
            # 流入0かつ未訪問なら
            bfs(u) # uからBFS
    
    return ret

L = topological_sort(G,indeg.copy())
dp = [0]*(N+1)
for i in range(N):
    node = L[i]
    for nx in G[node]:
        dp[nx] = max(dp[nx], dp[node]+1)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N,M=map(int, input().split())
G = {i: [] for i in range(1, N+1)}
deg = [0]*(N+1)
for _ in range(M):
    x,y=map(int,input().split())
    G[x].append(y)
    deg[y] += 1

from collections import deque, defaultdict
S = [i for i in range(1, N+1) if deg[i]==0]
dp = [0]*(N+1)

def topological_sort(adj, indeg):
    """
    幅優先探索によるトポロジカルソート
    O(|V|+|E|)

    adj: 隣接リスト
    indeg: 各ノード入次数を管理するリスト

    ret: トポロジカルソートされたリスト
    """
    is_visited = [0]*(N+1)
    ret = []
    def bfs():
        """
        sからBFSする
        """
        queue = deque(S)
        while queue:
            u = queue.popleft()
            # queueには入次数0のノードが入っているのでretに追加
            # ret.append(u)

            for v in adj[u]: # uの子ノードを探索
                indeg[v] -= 1 #探索したら子の次数を減らす
                if (indeg[v] == 0):
                    # 入次数0かつ未訪問なら
                    queue.append(v)
                    dp[v] = max(dp[v], dp[u]+1)
                    is_visited[v] = 1
    
    bfs()
    
    # return ret

topological_sort(G, deg)
print(max(dp))

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    N, M = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    deg = [0]*N
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        deg[b-1] += 1

    dist = [10**6]*(N)

    def topological_sort():
        """
        deg[i] := 頂点iの入次数
        グラフ入力時に計算
        """
        que = deque()
        for i in range(N):
            if deg[i] == 0:
                que.append(i)
                dist[i] = 0

        while que:
            u = que.popleft()
            for v in G[u]:
                deg[v] -= 1
                if deg[v] == 0:
                    que.append(v)
                    dist[v] = dist[u] + 1

    topological_sort()

    print(max(dist))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)
INF=float('inf')

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

def f(k):
  if dp[k]!=-1:
    return dp[k]
  
  dp[k]=0
  if adj[k]:
    for v in adj[k]:
      dp[k]=max(dp[k],f(v)+1)
  return dp[k]

ans=-INF  
for i in range(1,n+1):
  ans=max(ans,f(i))

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(M):
  a,b=map(int,input().split())
  G[b-1].append(a-1)
DP=[-1]*N
def f(x):
  if DP[x]!=-1:
    return DP[x]
  DP[x]=0
  for i in range(len(G[x])):
    DP[x]=max(DP[x],f(G[x][i])+1)
  return DP[x]

for i in range(N):
  f(i)
print(max(DP))

Submission status: Accepted

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

def dfs(v):
    if dp[v] != 0: return dp[v]
    cnt = 0
    for i in g[v]:
        cnt = max(cnt, dfs(i) + 1)
    dp[v] = cnt
    return dp[v]

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

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

print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
list_edge = [[] for _ in range(N)]
deg = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    list_edge[a-1].append(b-1)
    deg[b-1] += 1
que = deque()
for v in range(N):
    if deg[v]==0:
        que.append(v)
dp = [0]*N
while que:
    v = que.popleft()
    list_nv = list_edge[v]
    for nv in list_nv:
        deg[nv] -= 1
        if deg[nv]==0:
            que.append(nv)
            dp[nv] = max(dp[v],dp[v]+1)
print(max(dp))

Submission status: Accepted

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

def longest_path(s):
    global dp
    if dp[s-1]<1:
        if edge[s]:
            dp[s-1]=max((longest_path(t)+1)for t in edge[s])
        else:
            dp[s-1]=0
    return dp[s-1]

N,M=map(int,input().split())
edge={}
for i in range(1,N+1):
    edge.setdefault(i,[])
for _ in range(M):
    x,y=map(int,input().split())
    edge[x].append(y)
dp=[0]*N
for i in range(1,N+1):
    if dp[i-1]==0:
        longest_path(i)

print(max(dp))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
to = [False]*N
for i in range(M):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  to[b-1] = True

import sys
sys.setrecursionlimit(10**8)

def dfs(v):
  if lis[v]>=0:
    return lis[v]
  if len(edge[v])==0:
    lis[v] = 1
    return 1
  ans = 0
  for u in edge[v]:
    ans = max(ans, dfs(u))
  lis[v] = ans+1
  return ans+1

ans = 0
lis = [-1]*N
for r in range(N):
  if to[r]==False:
    ans = max(ans, dfs(r)-1)
print(ans)

Submission status: Accepted

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

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

dp = [-1]*(n+1)
# dp[i]:頂点iに到達したときの有向辺の最長の長さ
def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    res = 0
    for nx in G[cur]:
        res = max(res,dfs(nx)+1)
    dp[cur] = res
    return res
    
for i in range(n):
    dp[i] = max(dp[i],dfs(i))

print(max(dp))

Submission status: Accepted

Solution code:
#%%
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
#%%
for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)

#%%
ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


def ifvalid(i):
    if i < 0:
        return False
    return True


from sys import setrecursionlimit
setrecursionlimit(1000000)



def solve():
    n,m=sep()
    g=[[] for i in range(n+5)]
    for i in range(m):
        a,b=sep()
        a-=1
        b-=1
        g[a].append(b)
    dp=[-1 for i in range(n+5)]

    def dfs(v):
        if not g[v]:
            dp[v] = 0
            return
        if dp[v]!=-1:
            return
        for c in g[v]:
            dfs(c)
            dp[v] = max(dp[v], 1 + dp[c])
        return

    for v in range(n):
        if dp[v]==-1:
            dfs(v)

    print(max(dp))


solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [[-1] for _ in range((n + 1))]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    y[x_in].append(y_in)
    d.append((x_in, y_in))

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


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in in y[i][1:]:
            tmp = dp(x_in) + 1
            if tmp > ret:
                ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

print("{}".format(ans))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

def get(i, value, vis):
    if vis[i]:
        return value[i]
    vis[i] = True
    ans = 0
    for j in adj[i]:
        ans = max(ans, 1+get(j, value, vis))
    value[i] = ans
    return ans


n, m = map(int, input().split())
adj = {}
for i in range(n):
    adj[i] = []
for i in range(m):
    x, y = map(int,input().split())
    adj[x-1].append(y-1)
vis = [False for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    value[i] = get(i, value, vis)
x = 0
for i in value:
    x = max(x, i)
print(x)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

def get(i, value, vis):
    if vis[i]:
        return value[i]
    vis[i] = True
    ans = 0
    for j in adj[i]:
        ans = max(ans, 1+get(j, value, vis))
    value[i] = ans
    return ans


n, m = map(int, input().split())
adj = {}
for i in range(n):
    adj[i] = []
for i in range(m):
    x, y = map(int,input().split())
    adj[x-1].append(y-1)
vis = [False for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    value[i] = get(i, value, vis)
x = 0
for i in value:
    x = max(x, i)
print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
indeg = [0] * N
for x,y in XY:
    x,y = x-1,y-1
    es[x].append(y)
    indeg[y] += 1

from collections import deque
q = deque()
for i in range(N):
    if indeg[i] == 0:
        q.append(i)

dp = [0] * N
while q:
    v = q.popleft()
    for to in es[v]:
        indeg[to] -= 1
        if indeg[to] == 0: q.append(to)
        dp[to] = max(dp[to], dp[v] + 1)

print(max(dp))

Submission status: Accepted

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

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

def rec(v):
  if dp[v] != -1:
    return dp[v]
  res = 0
  for next_v in G[v]:
    res = max(res, rec(next_v)+1)
  dp[v] = res
  return dp[v]
  
for i in range(N):
  dp[i] = rec(i)
  
print(max(dp))

Submission status: Accepted

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

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

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

for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append(y)
    #xy[y].append(x)
    
#xy = [[int(i)-1 for i in input().split()] for j in range(m)]
chk = [0]*n
dp = [0]*n

#print(xy)

def f(x):
    #global dp,chk
    if chk[x] == 1:
        return dp[x]
    fans = 0
    chk[x] = 1
    for i in range(len(xy[x])):
        fans = max(fans,f(xy[x][i])+1)
    dp[x] = fans
    #print(dp,chk)
    return dp[x]

ans = 0

for i in range(n):
    ans = max(ans,f(i))
    #print(f(i))
    
#print(dp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


n,m=L()
A=[L() for i in range(m)]
g=[[] for i in range(n+1)]
for x,y in A:
    g[x].append(y)

vis=[0 for i in range(n+1)]
dp=[-1 for i in range(n+1)]
def rec(v):
    if vis[v]:
        return dp[v]
    best=0
    vis[v]=1
    for neigh in g[v]:
        best=max(best,rec(neigh)+1)
    dp[v]=best
    return best
best=0
for i in range(1,n+1):
    best=max(best,rec(i))
print(best)




endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Accepted

Solution code:
# DAGの最長経路...トポロジカルソートもどきか？
# 普通にDAGに沿ったdpをすればいいのでは?
# 再帰だと実装楽そうだけどどうしよう
# 問題は終了と最初がわからんこと
# いや最初は全部長さ0をセットすればいいだろ
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


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


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, M = ints()
dag = defaultdict(lambda: [])
indeg = [0] * N
for _ in ra(M):
    x, y = mina(*ints())
    indeg[y] += 1
    dag[x].append(y)

q = deque()
for u, inn in enu(indeg):  # 多点DFS初期化
    if inn == 0:
        q.append((u, 0))

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u, l = q.popleft()
    # dp[u] = max(dp[u], l)
    dp[u] = l
    for nx in dag[u]:
        indeg[nx] -= 1
        if indeg[nx] == 0:
            q.append((nx, l + 1))
print(max(dp))