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 python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

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

dp = [-1]*n

def rec(node):
  if dp[node] != -1: return dp[node]
  result = 0
  for vi in G[node]:
    result= max(result,rec(vi)+1)
    dp[node] = result
  return result


for i in range(n):
  if dp[i] == -1:
      rec(i)
print(max(dp))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

def Topological_Sort(G):
    # DAGの隣接リストを受け取って、トポロジカルソートしたリストを返す
    V=len(G)
    div=[0]*V
    for gi in G:
        for ei  in gi:
            div[ei]+=1
    used=[0]*V
    result=[]

    def bfs(node):
        que = collections.deque([node])
        used[node] = 1
        while que:
            tmp = que.popleft()
            result.append(tmp)
            for v in G[tmp]:
                div[v] -= 1
                if div[v] == 0 and not used[v]:
                    que.append(v)
                    used[v] = 1

    for i in range(V):
        if div[i]==0 and not used[i]:
            bfs(i)
    return result
DAG = Topological_Sort(G)
dp=[0]*n
for ni in DAG:
  for vi in G[ni]:
    dp[vi] = max(dp[vi],dp[ni]+1)
print(max(dp))

Submission status: Accepted

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

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

    dag = [[] for _ in range(n+1)]
    for _ in range(m):
        src, dst = map(int, input().split())
        dag[src].append(dst)


    dists = [0] * (n+1)

    def longest(v):
        if dists[v]:
            return dists[v]
        for to in dag[v]:
            dists[v] = max(dists[v], longest(to) + 1)
        return dists[v]

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
 
sys.setrecursionlimit(150000)

def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]
 
    if G[n]==[]:
        dp[n]=0
        return 0
 
    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1
 
    return dp[n]
 
def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)
 
    dp=[-1]*N
 
    print(max(gdp(i, dp, G) for i in range(N)))
 
    return
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(150000)

def gdp(n, dp, G):
    if dp[n]!=-1:
        return dp[n]

    if G[n]==[]:
        dp[n]=0
        return 0

    for i in G[n]:
        ll=gdp(i, dp, G)
        if dp[n]<ll+1:
            dp[n]=ll+1

    return dp[n]

def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    G=[[] for _ in range(N)]
    for i in range(M):
        G[x[i]-1].append(y[i]-1)

    dp=[-1]*N

    print(max(gdp(i, dp, G) for i in range(N)))

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    parents = [0] * (n+1)
    for _ in range(m):
        src, dst = map(int, input().split())
        graph[src].append(dst)
        parents[dst] += 1

    q = deque()
    for i in range(1, n+1):
        if parents[i] == 0:
            q.append(i)

    dists = [0] * (n+1)
    for i in q:
        dists[0] = 0

    while q:
        at = q.popleft()
        for to in graph[at]:
            parents[to] -= 1
            if parents[to] == 0:
                q.append(to)
                dists[to] = dists[at] + 1

    print(max(dists[1:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
 
n, m = map(int, input().split())
 
edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)
 
dp = [-1 for _ in range(n+1)]
 
def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d
 
for u in range(1, n+1):
    longest_path(u)
 
print(max(dp))

Submission status: Accepted

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

def main():
    n,m=map(int,input().split())
    g1=[[] for _ in range(n+1)]
    g2=[0]*(n+1)
    for i in range(m):
        a,b=map(int,input().split())
        g1[a].append(b)
        g2[b]+=1
    st=deque([])
    for i in range(n+1):
        if g2[i]==0:
            st.append(i)
    d=[10**5+1]*(n+1)
    for i in st:
        d[i]=0
    while st:
        a=st.popleft()
        for b in g1[a]:
            g2[b]-=1
            if g2[b]==0:
                st.append(b)
                d[b]=d[a]+1
    print(max(d[1:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
dp = [-1 for _ in range(n)]

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


def dfs(s):
    #print(s, dp)
    if dp[s] != -1:
        return dp[s]
    
    rep = 0
    for g in graph[s]:
        rep = max(rep, dfs(g)+1)
    dp[s] = rep
    return rep

#print(graph)
ans = 0
for i in range(n):
    #print('i:', i)
    ans = max(ans, dfs(i))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#bfsするからdequeじゃないとだめ
from collections import deque
n,m=map(int,input().split())
infi=10**10
#topological sort
#通常のグラフ構成のグラフ
graph1=[[]for _ in range(n+1)]
#入ってくる辺の数を記録するグラフ
graph2=[ 0 for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    graph1[x].append(y)
    graph2[y]+=1
#start地点になるのは入ってくる辺の数が0の点
start=deque([])
for i in range(1,n+1):
    if graph2[i]==0:
        start.append(i)
#start地点から
#①topoリストに加える
#②隣接点の入ってくる辺の数を減らす
#③入ってくる辺の数が0になったらstartに加える
#を繰り返す
#※今回はtopoに加えるのは本質ではない。
#topoに加えていく順序で見ていきながら距離を入れていく。
# topo=[]
dist=[infi]*(n+1)
for i in start:
    dist[i]=0
while start:
    a=start.popleft()
    kyori=dist[a]
#     topo.append(a)
    for b in graph1[a]:
        graph2[b]-=1
        if graph2[b]==0:
            start.append(b)
            dist[b]=min(dist[b],dist[a]+1)
print(max(dist[1:]))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000000)
from collections import defaultdict
from collections import deque
# starting with start node and then looking for the kids
# and the solving the sub-problem with kids
def recursive_dfs(graph, start_node, map1):
  if start_node not in graph:
    map1[start_node] = 0
    return 0
  dist = 0
  for child in graph[start_node]:
    if child not in map1:
      dist = max(recursive_dfs(graph, child, map1), dist)
    else:
      dist = max(map1[child], dist)
  map1[start_node] = dist + 1
  #print(map1)
  return (dist + 1)
 
N,M = [int(i) for i in input().split()] # nodes, edges
graph = defaultdict(list)
for i in range(M):
  s,d = [i for i in input().split()]
  graph[s].append(d)
map1 = defaultdict(int)
ans = 0
for i in range(1, N+1):
  if i in map1:
    ans = max(ans, map1[str(i)])
  else:
    ans = max(recursive_dfs(graph, str(i), map1), ans)
print("%s" % ans)

Submission status: Accepted

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

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

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


def dfs(s):
    if F[s] != -1:
        return F[s]
    ret = 0
    for g in G[s]:
        ret = max(ret, dfs(g)+1)
    F[s] = ret
    return ret


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

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def main():
  n, m = map(int, input().strip().split())
  memo = [-1] * (n+1)
  graph = defaultdict(list)

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

  def rec(v):
    if memo[v] != -1:
      return memo[v]

    lp = 0
    for t in graph[v]:
      lp = max(lp, rec(t)+1)
    memo[v] = lp
    return memo[v]

  lp = 0
  for v in range(1, n+1):
    lp = max(lp, rec(v))
  print(lp)


if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	n,m=map(int,input().split())
	
	inc=[0]*(n)
	out=[[] for _ in range(n)]
	
	for i in range(m):
		x,y=map(int,input().split())
		inc[y-1]+=1
		out[x-1].append(y-1)
	
	q={i for i,c in enumerate(inc) if c==0}
	C=[]
	
	while q:
		k=q.pop()
		C.append(k)
		for i in out[k]:
			inc[i]-=1
			if inc[i]==0:
				q.add(i)
	
	ans=[0]*n
	
	for i in C:
		for j in out[i]:
			ans[j]=max(ans[j],ans[i]+1)
	
	
	print(max(ans))
	
	
	
if __name__ == "__main__":
	main()

Submission status: Accepted

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

    def dfs(v):
        """最長有向パスに含まれる頂点数"""
        if memo[v] != -1:
            return memo[v]

        ret = 0
        for u in g[v]:
            ret = max(ret, dfs(u))
        ret += 1  # 自身
        memo[v] = ret
        return ret

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

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

    memo = [-1] * n

    ret = 0
    for i in range(n):
        ret = max(ret, dfs(i))
    print(ret - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque


def solve():
    N, M = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    G = defaultdict(list)
    in_edge = [0] * N
    for x, y in zip(m, m):
        G[y-1].append(x-1)
        in_edge[x-1] += 1

    dp = [0] * N
    q = deque(i for i, x in enumerate(in_edge) if not x)
    q_enqueue = q.append
    q_dequeue = q.popleft
    while(q):
        x = q_dequeue()
        for j in G[x]:
            in_edge[j] -= 1
            if not in_edge[j]:
                q_enqueue(j)
                if dp[j] < dp[x] + 1:
                    dp[j] = dp[x] + 1
    return max(dp)


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Accepted

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

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, m = na()
memo = [-1] * n
def dp(v):
    if memo[v] != -1:
        return memo[v]
    if G[v]:
        memo[v] = max(dp(i) for i in G[v]) + 1
    else:
        memo[v] = 0
    return memo[v]


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)

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

in_ = set()
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    in_.add(b)

dist = [-1]*n

from collections import deque
def dfs(cur):
    if dist[cur] != -1:
        return dist[cur]
    r = 0
    for to in G[cur]:
        r = max(r, dfs(to)+1)
    dist[cur] = r
    return r

for i in range(n):
    if i in in_:
        continue
    dfs(i)

ans = max(dist)

print(ans)

Submission status: Accepted

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

def search(index: int, dp: list, graph: list) -> int:
    if dp[index] != -1:
        return dp[index]+1

    tmp = 0
    for d in graph[index]:
        tmp = max(tmp, search(d, dp, graph))

    dp[index] = tmp
    return tmp+1


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

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

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

ans = 0
for i in range(N):
    ans = max(ans, search(i, dp, graph))

print(ans-1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1 - 1].append(v2 - 1)
    ins[v2 - 1] += 1

# 入次数がゼロのノードから始める
q = deque(v1 for v1 in range(n) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
            
LP = {v:0 for v in res}
for v0 in res:
    for v1 in outs[v0]:
        LP[v1] = max(LP[v1], LP[v0] + 1)
print(max(LP.values()))

Submission status: Accepted

Solution code:
#topological sort
from collections import deque,defaultdict
#n:ノードの数　m:エッジ辺の数
n,m=map(int,input().split())
#m個の有向辺　xi -> yi
edges=[tuple(map(int,input().split())) for i in range(m)]

in_cnt=defaultdict(int) #i番目のノードの入力辺の数
outs=defaultdict(list) #i番目のノードからi0,i1,i2,・・・番目のノードに辺が存在する時outs{i:[i0,i1,i2・・・]}

for out_node,in_node in edges:
    in_cnt[in_node-1]+=1
    outs[out_node-1].append(in_node-1)

topo_sort=[] #ソートされた結果を代入する
q=deque([i for i in range(n) if in_cnt[i]==0]) #入力の存在しないノードを入れる

dp=[0]*n
while q:
    v1=q.popleft()
    topo_sort.append(v1)
    for v2 in outs[v1]:
        in_cnt[v2]-=1
        dp[v2]=dp[v1]+1
        if in_cnt[v2]==0:
            q.append(v2)
print(max(dp))

Submission status: Accepted

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

N,M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    G[x].append(y)
#G[i]は頂点iから辺でつながっている頂点のlist
def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)
    
    for i in range(len(g)):
        if i not in visited:
            dfs(i)
        
    return topological_list[::-1]

T = topological_sort(G)
dist = [0]*N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v],dist[n]+1)       
        
print(max(dist))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
n, m = map(int, input().split())
g = [[] for _  in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  x, y = x -1, y-1
  g[x].append(y)  
 
# dp[v]: ノードvを起点にしたときの、Gの有効パスの長さの最大値
dp = [-1]*n
def rec(v):
  if dp[v] != -1:
    return dp[v]
  else:
    res = 0
    for u in g[v]:
      res = max(res, rec(u)+1)
    dp[v] = res
    return dp[v]
  
for i in range(n):
  rec(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

# dp[v]: ノードvを起点にしたときの、Gの有効パスの長さの最大値
dp = [-1]*n
def rec(v):
  if dp[v] != -1:
    return dp[v]
  else:
    res = 0
    for u in g[v]:
      res = max(res, rec(u)+1)
    dp[v] = res
    return dp[v]
  
for i in range(n):
  rec(i)
print(max(dp))

Submission status: Accepted

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

def rec(v):
 if memo[v]!=-1:
  return memo[v]

 res=0
 for nv in tree[v]:
  res=max(res,rec(nv)+1)

 memo[v]=res
 return res

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

tree=[[] for i in range(n)]
memo=[-1 for i in range(n)]

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

ans=0
for v in range(n):
 ans=max(ans,rec(v))
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)]
memo=[-1 for i in range(n)]

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

def rec(x):
 if memo[x]!=-1:
  return memo[x]

 res=0
 for i in g[x]:
  res=max(res,rec(i)+1)

 memo[x]=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(2*10**5)


def dfs(v, graph, memo):
    if memo[v] != -1:
        return memo[v]
    ret = 0
    for c in graph[v]:
        ret = max(ret, dfs(c, graph, memo) + 1)
    memo[v] = ret
    return ret


def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        graph[x].append(y)
    memo = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, dfs(i, graph, memo))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


def create_graph(V: int, edges: np.array, dtype=None):
    """csr_matrix を作成する

    もし精度が足りない場合は dtype=object にする。
    """
    return csr_matrix((edges[:, 2], (edges[:, 0], edges[:, 1])),
                      shape=(V, V), dtype=dtype)


def main() -> None:
    N, M = map(int, input().split())
    edges = []
    adj_list = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        edges.append([x-1, y-1, 1])
        adj_list[x-1].append(y-1)
    graph = create_graph(N, np.asarray(edges))
    _, labels = connected_components(
        csgraph=graph, directed=True,
        connection="strong", return_labels=True)
    order = [(x, i) for i, x in enumerate(labels)]
    order.sort(reverse=True)
    dp = [0] * N
    for _, i in order:
        for v in adj_list[i]:
            dp[v] = max(dp[v], dp[i] + 1)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def path(start):
    if dp[start]!=-1:
        return dp[start]
    visited[start]=1
    maxi=-1
    for i in adjacency_list[start]:
        maxi=max(maxi,path(i))
    dp[start]=maxi+1
    return dp[start]
N,M=map(int,input().split())
dp=[-1]*(N+1)
visited=[0]*(N+1)
adjacency_list=[]
for i in range(N+1):
    adjacency_list.append([])
# print(adjacency_list)
for r in range(M):
    u,v=map(int,input().split())
    adjacency_list[u].append(v)
# print(adjacency_list)
for i in range(1,N+1):
    if len(adjacency_list[i])==0:
        dp[i]=0
# print(dp)
for i in range(1,N+1):
    if (visited[i]==0):
        path(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=list(s)
    memo=[0]*N
    def saiki(v):
        if memo[v]:
            return memo[v]
        tmp=0
        for nv in edge[v]:
            memo[v]=max(memo[v],saiki(nv)+1)
            tmp=max(tmp,memo[v])
        return tmp
    ans=0
    for v in que:
        ans=max(ans,saiki(v))
    print(ans)
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
xy = [[int(i)-1 for i in input().split()] for _ in range(M)]

cnt = [0] * N
v = [[] for _ in range(N)]
for x, y in xy :
  v[x].append(y)
  cnt[y] += 1
  
s = []
for i in range(N) :
  if cnt[i] == 0 :
    s.append(i)

dp = [0] * N
while s :
  cur = s.pop()
  for nex in v[cur] :
    dp[nex] = max(dp[nex], dp[cur] + 1)
    cnt[nex] -= 1
    if cnt[nex] == 0 :
      s.append(nex)
      
print(max(dp))

Submission status: Accepted

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

# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+10)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[[]for _ in range(n)]
c=[0]*n
import sys
sys.setrecursionlimit(10**6)
for i in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)
from functools import lru_cache
@lru_cache(maxsize=n)
def l(k):
    return max([l(i)for i in p[k]]+[0])+1
print(max([l(i)for i in range(n)])-1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 100)

def rec(v, dp, E):
    if dp[v] != -1:
        return dp[v]
    x = 0
    for w in E[v]:
        x = max(x, rec(w, dp, E) + 1)
    dp[v] = x
    return x

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

dp = [-1 for _ in range(n)]
ans = 0
for i in range(n):
    ans = max(ans, rec(i, dp, E))
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inc = [0]*n
out = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  out[a].append(b)
  inc[b] += 1

S = {i for i, c in enumerate(inc) if c == 0}
L = []
 
while S:
    k = S.pop()
    L.append(k)
    for m in out[k]:
        inc[m] -= 1
        if inc[m] == 0:
            S.add(m)

dp = [0]*n
for i in L:
  for j in out[i]:
    dp[j] = max(dp[j], dp[i]+1)
print(max(dp))

Submission status: Accepted

Solution code:
V,m = map(int,input().split())

from collections import defaultdict
g = defaultdict(list)
deg = defaultdict(int)
for _ in range(m):
    x,y = map(int,input().split())
    g[x-1].append(y-1)
    deg[y-1] += 1
    
# V: 頂点数
# G[v] = [w, ...]:
#    有向グラフ上の頂点vから到達できる頂点w
# deg[v]:
#    頂点vに到達できる頂点の数

from collections import deque
ans = list(v for v in range(V) if deg[v]==0)
deq = deque(ans)
used = [0]*V
while deq:
    v = deq.popleft()
    for t in g[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)

# ans: トポロジカル順序に並べた頂点

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

for a in ans:
    for b in g[a]:
        dp[b] = dp[a] + 1

print(max(dp))

Submission status: Accepted

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examG()

"""

"""

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n,m = mii()

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


for i in range(m):
    x,y = mii()
    arr[x-1].append(y-1)
    deg[y-1]+=1

# V: 頂点数
# G[v] = [w, ...]:
#    有向グラフ上の頂点vから到達できる頂点w
# deg[v]:
#    頂点vに到達できる頂点の数

ans = list(i for i in range(n) if deg[i]==0)
deq = deque(ans)
used = [0]*m

while deq:
    v = deq.popleft()
    for t in arr[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)
#print(ans)
# ans: トポロジカル順序に並べた頂点

#ans：遷移前
for i in ans:
    ari = arr[i]
    #j：遷移後の座標を出す
    for j in range(len(ari)):
        dp[ari[j]] = max(dp[i]+1,dp[ari[j]])
    
print(max(dp))

Submission status: Accepted

Solution code:
#G-not再帰
import queue
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
adj=[[] for _ in range(N)]
deg_in=[0]*N#各頂点の入力次数

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    adj[x].append(y)
    deg_in[y]+=1
    
dp=[0]*N#i番目からみた最長経路
L=[]#トポロジカルソート後
q=queue.Queue()#入力辺を持たないノード

for i in range(N):
    if deg_in[i]==0:
        q.put(i)

while not q.empty():
    v=q.get()
    L.append(v)
    for to in adj[v]:
        deg_in[to]-=1
        if deg_in[to]==0:
            q.put(to)
            dp[to]=max(dp[to],dp[v]+1)
        
print(max(dp))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, readline().split())
outdeg = {i: [] for i in range(N)}
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    outdeg[a].append(b)

dp = [-1] * (N)


def rec(s):
    if dp[s] != -1:
        return dp[s]

    res = 0
    for t in outdeg[s]:
        res = max(res, rec(t)+1)
    dp[s] = res
    return res


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