Problem:


Score : 100 points

Problem Statement

There is a directed graph G with N vertices and M edges.
The vertices are numbered 1, 2, \ldots, N, and for each i (1 \leq i \leq M), the i-th directed edge goes from Vertex x_i to y_i.
G does not contain directed cycles.

Find the length of the longest directed path in G.
Here, the length of a directed path is the number of edges in it.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq x_i, y_i \leq N

All pairs (x_i, y_i) are distinct.

G does not contain directed cycles.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the length of the longest directed path in G.

Sample Input 1

4 5
1 2
1 3
3 2
2 4
3 4

Sample Output 1

3

The red directed path in the following figure is the longest:

Sample Input 2

6 3
2 3
4 5
5 6

Sample Output 2

2

The red directed path in the following figure is the longest:

Sample Input 3

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3

Sample Output 3

3

The red directed path in the following figure is one of the longest:



Sample input:
4 5
1 2
1 3
3 2
2 4
3 4


Sample output:
3

Submission status: Accepted

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

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

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    adj[x].append(y)
    
dp=[0]*N#i番目絡みた最長経路

def rec(ii):
    new=0
    if len(adj[ii])==0:
        return 0
    for to in adj[ii]:
        if dp[to]!=0:
            new=dp[to]
        else:
            new=rec(to)
        dp[ii]=max(new+1,dp[ii])
    return dp[ii]
        
for i in range(N):
    rec(i)
    
print(max(dp))

Submission status: Accepted

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

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

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    adj[x].append(y)
    
dp=[-1]*N#i番目絡みた最長経路
for i in range(N):
    if len(adj[i])==0:
        dp[i]=0

def rec(ii):
    new=0
    for to in adj[ii]:
        if dp[to]!=-1:
            new=dp[to]
        else:
            new=rec(to)
        dp[ii]=max(new+1,dp[ii])
    return dp[ii]
        
for i in range(N):
    rec(i)
    
print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque
import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
dp = [-1 for i in range(n+1)]
def cul(x):
    if dp[x] != -1:
        return dp[x]
    else:
        if len(adjacent_list[x]) == 0:
            return 0
        dp[x] = max([cul(i) + 1 for i in adjacent_list[x]])
        return dp[x]
for i in range(1,n+1):
    cul(i)
print(max(dp))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 14:37:00 2020

@author: matsui
"""

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

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

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

while(len(st)):
    i=st[0]
    st.remove(st[0])
    
    ans.append(i)
    
    for j in g[i]:
        h[j]-=1
        if h[j]==0: 
            st.append(j)
            if dp[i]+1>dp[j]: 
                dp[j]=dp[i]+1
        
#print(ans)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque
 
N, M = map(int, input().split())
 
graph = [[] for i in range(N)]
to_this = [0] * N
for i in range(M):
  x, y = map(int, input().split())
  graph[x-1].append(y-1)
  to_this[y-1] += 1
 
 
depth = [0] * N
d = deque([i for i in range(N) if not to_this[i]])
while d:
  l = len(d)
  for i in range(l):
    node = d.popleft()
    children = graph[node]
    for child in children:
      to_this[child] -= 1
      if not to_this[child]:
        d.append(child)
      depth[child] = depth[node] + 1
 
print(max(depth))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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


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

    res = 0
    for child in graph[v]:
        res = max(res, dfs(child) + 1)
    dp[v] = res
    return res


def solve():
    ans = 0
    for v in range(1, N + 1):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import collections

input = sys.stdin.readline

def chmax(a,b):
	if a>b : 
		return a
	return b

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

que = collections.deque()
for v in range(N):
	if deg[v] == 0:
		que.append(v)

dp = [0]*N

while que:
	v = que.popleft()
	for nv in lst_edge[v]:
		deg[nv] -= 1
		if(deg[nv] == 0):
			que.append(nv)
			dp[nv] = chmax(dp[nv], dp[v]+1)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def solve(N, M, edges):
  outbound = defaultdict(deque)
  in_degree = defaultdict(int)
  for s,t in edges:
    outbound[s].append(t)
    in_degree[t] += 1

  q = deque()
  for i in range(N + 1):
    if in_degree[i] == 0:
      q.append(i)

  dp = [0 for _ in range(N + 1)]

  while q:
    node = q.popleft()
    for child in outbound[node]:
      dp[child] = max(dp[child], dp[node] + 1)
      in_degree[child] -= 1
      if in_degree[child] == 0:
        q.append(child)

  print(max(dp))


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


N, M = iln()
edges = []
for i in range(M):
  edges.append(iln())
  
solve(N, M, edges)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline

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

dp = [-1] * N

def rec(v):
	if dp[v] != -1:
		return dp[v]
	ans = 0
	lst_nv = lst_edge[v]
	for nv in lst_nv:
		ans = max(ans, rec(nv)+1)
	dp[v] = ans
	return dp[v]

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

Submission status: Accepted

Solution code:
#Educational DP Contest
#G-LongestPath

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

#dp table
dp = [0]*n

#graph table
#頂点aから頂点bに向かう時、テーブルaに頂点bの情報を入れる。
#これを隣接リストという。(<>隣接行列)
edge = [[] for _ in range(n)]

#またこれに対し、頂点iに何本のノードが向かってきているかを保持
to = [0]*n

#process1(graph process)
#This graph is unweighted.
for i in range(m): #mノード
    a,b = map(int,input().split())
    a,b = a-1,b-1
    
    edge[a].append(b)
    to[b] += 1


#process2(search top process)
#toが0のノードをリストアップ
#toが0→始点or使わないということ
#ここから始めることで最長距離が求まることが証明できるので、これを回す
st = []
for i,j in enumerate(to):
    if j == 0:
        st.append(i)


#process3(dp process)
while len(st):
    go = st.pop()
    for e in edge[go]: #egde[go]=始点から向かっている方向のリスト
        to[e] -= 1 #向かってきているノードを一つ消す(これがdp[go]+1できる条件)
        if to[e] == 0: #toがなくなるということは、始点の対象になるということ
            st.append(e)
        dp[e] = max(dp[e],dp[go]+1) #go→eのeには、max(もともとの値,go+1の値)が入る
        #これをst(始点)がなくなるまで続けたときのdpの最大値がans


#output process
print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque

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

xy = []

dic = {}
pnum = [0] * N

for i in range(M):

    x,y = map(int,input().split())
    x -= 1
    y -= 1

    if x not in dic:
        dic[x] = []

    dic[x].append(y)
    pnum[y] += 1

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

for i in range(N):

    if pnum[i] == 0:
        q.append(i)

#print (q)
#print (dic)

while len(q) > 0:

    now = q.popleft()

    if now not in dic:
        continue

    for i in dic[now]:

        if dp[i] < dp[now] + 1:
            dp[i] = dp[now] + 1

        pnum[i] -= 1
        if pnum[i] == 0:
            q.append(i)


print (max(dp))

Submission status: Accepted

Solution code:
import random
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)

N, M = map(int, raw_input().split())
# N, K = 5000, 100
AN = defaultdict(list)
for i in range(M):
    u, v = map(int, raw_input().split())
    AN[u].append(v)
longest_path_from_vertex_cache = {}

def get_longest_path(V):


    if V in longest_path_from_vertex_cache:
        return longest_path_from_vertex_cache[V]

    adjacent_vertices = AN[V]
    longest_path = 0
    for vertex in adjacent_vertices:
        current_path_len = 1 + get_longest_path(vertex)
        if longest_path < current_path_len:
            longest_path = current_path_len

    longest_path_from_vertex_cache[V] = longest_path
    return longest_path

print max(get_longest_path(vertex) for vertex in range(1, N+1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
 
n, m = map(int, input().split())
 
d = defaultdict(list)
for i in range(m):
  tx, ty = map(int, input().split())
  d[tx-1].append(ty-1)
  
dp = [0]*n
 
def dist(i):
  if dp[i] > 0:
    return dp[i]
  dp[i] = 0
  for ni in d[i]:
    dp[i] = max([dp[i], dist(ni)+1])
  return dp[i]
 
ans = 0
for i in range(n):
  ans = max(ans, dist(i))
    
print(ans)

Submission status: Accepted

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

from collections import deque

tpsort = [v for v in range(N) if len(E2[v]) == 0]
q = deque(tpsort)
while q:
    t = q.popleft()
    for v in E[t]:
        d[v] -= 1
        if d[v] == 0:
            q.append(v)
            tpsort.append(v)

dp = [0]*N
for v in tpsort:
    for par in E2[v]:
        dp[v] = max(dp[v], dp[par]+1)

print(max(dp))

Submission status: Accepted

Solution code:
from sys import stdin, exit, setrecursionlimit
setrecursionlimit(100000000)

input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())
si = lambda: input().strip('\n')
ssi = lambda: input().strip('\n').split()


def dfs(node):
    if len(graph[node]) == 0:
        dp[node] = 0
        return 0
    if dp[node] != -1: return dp[node]
    ans = 0
    for i in graph[node]:
        ans = max(ans, dfs(i)+1)
    dp[node] = ans
    return ans


n, m = mi()
graph= [[] for i in range(n+1)]
for i in range(m):
    a, b = mi()
    graph[a].append(b)
dp = [-1]*(n+1)
for i in range(1, n+1):
    if dp[i] == -1:
        dfs(i)
print(max(dp))

Submission status: Accepted

Solution code:
import math
import sys
import collections
import sys

sys.setrecursionlimit(200000)




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

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

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


    res = 0
    for nv in di[v]:
        res = max(rec(nv) + 1 ,res)  # × dp[nv] ○ rec(nv) ∵ dp[nv]が未計算の場合があるから
    dp[v] = res
    return res

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

# print(qs)
di = collections.defaultdict(lambda :[])
for q in qs:
    x,y = q
    di[x].append(y)
    #dp[y] → yを終点としたlongest path

for i in range(N + 1):
    rec(i)
print(max(dp))

Submission status: Accepted

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

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

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


dp = [-1] * N

def rec_calc_depth(i):
  global dp
  if dp[i] >= 0:
    return dp[i]
  else:
    children = graph[i]
    depth = 0
    for child in children:
      depth = max(depth, rec_calc_depth(child)+1)
    
    dp[i] = depth
    return depth

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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


depth = [0] * N
d = deque([i for i in range(N) if not to_this[i]])
while d:
  l = len(d)
  for i in range(l):
    node = d.popleft()
    children = graph[node]
    for child in children:
      to_this[child] -= 1
      if not to_this[child]:
        d.append(child)
        depth[child] = depth[node] + 1

print(max(depth))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
edges = [[] for _ in range(n)]
edges2 = [0] * n

dis = [0] * n

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

q = []

for i in range(n):
    if dis[i] == 0:
        q.append(i)

while q:
    l = q.pop(0)
    for i in edges[l]:
        dis[i] = max(dis[i], dis[l] + 1)
        edges2[i] -= 1
        if edges2[i] == 0:
            q.append(i)

print(max(dis))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

dis = [0] * n

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

q = []

for i in range(n):
    if dis[i] == 0:
        q.append(i)

while q:
    l = q.pop(0)
    for i in edges[l]:
        dis[i] = max(dis[i], dis[l] + 1)
        edges2[i].remove(l)
        if not edges2[i]:
            q.append(i)

print(max(dis))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  # x -> y
        adj_list[y].append(x)

    state = [0] * n
    distances = [0] * n
    stack = deque(range(n))

    while stack:
        x = stack.pop()
        if state[x] == 0:
            state[x] = 1
            stack.append(x)
            stack.extend(adj_list[x])
        elif state[x] == 1:
            state[x] = 2
            if adj_list[x]:
                distances[x] = max(distances[y] for y in adj_list[x]) + 1

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

graph = [[] for _ in range(n)]
out_deg = [0] * n
dp = [0]*n

for x, y in xy:
    graph[y-1].append(x-1)
    out_deg[x-1] += 1

stack = deque([i for i in range(n) if out_deg[i] == 0])

while stack:
    node = stack.popleft()
    for i in graph[node]:
        dp[i] = max(dp[i], dp[node]+1)
        out_deg[i] -= 1
        if out_deg[i] == 0:
            stack.append(i)

print(max(dp))

Submission status: Accepted

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

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

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

dp = [0]*N


def dist(v):
    if dp[v] > 0:
        return dp[v]
    dp[v] = 0
    for nv in h[v]:
        dp[v] = max([dp[v], dist(nv)+1])
    return dp[v]


ans = 0
for v in range(N):
    ans = max([ans, dist(v)])

print(ans)

Submission status: Accepted

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

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

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

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

dp = [0 for _ in range(n)]
q = deque([])

for i in range(n):
    if indeg[i] == 0:
        q.append(i)

while q:
    v = q.popleft()
    for w in g[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            q.append(w)
            dp[w] = max(dp[w], dp[v]+1)

print(max(dp))

Submission status: Accepted

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

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

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

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

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


def LP(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for w in g[v]:
        ans = max(ans, LP(w)+1)
    dp[v] = ans
    return dp[v]


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

print(max(dp))

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]

vs = set()
dvs = [0 for _ in range(N+1)]
def dfs_w(v, d):
    # dfs while版 
    stack = [v]
    path = []
    cd=ld= 0
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v in vs:
            p = stack.pop()
            dvs[-p] = max(dvs[-p], dvs[v]+1)
            continue
        if v < 0:
            c = path.pop()
            dvs[-v] = max(dvs[-v], dvs[c]+1)
            cd -= 1
        else:
            vs.add(v)
            path.append(v)
            ld = max(ld, cd)
            cd += 1
            for u in d[v]:
                stack += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    d[a].add(b)

for i in range(N):
    i += 1
    if i in vs:
        continue
    dfs_w(i, d)
print(max(dvs))

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def zrob_listy_sadziedztwa(lista): 
    listy_sasiedzitwa = {}
    for x, y in lista: 
        listy_sasiedzitwa[x] = []
        listy_sasiedzitwa[y] = []
    for x, y in lista: 
        listy_sasiedzitwa[y].append(x)
    return listy_sasiedzitwa

def wyjscie_do_szkoly_bfs(lista_zasad): 
    zasady = {}
    ile_niespelnionych = {}
    for rzecz1,rzecz2 in lista_zasad: 
        zasady[rzecz1] = [] 
        zasady[rzecz2] = []
        ile_niespelnionych[rzecz1] = 0 
        ile_niespelnionych[rzecz2] = 0
    for rzecz1, rzecz2 in lista_zasad: 
        zasady[rzecz1].append(rzecz2)
        ile_niespelnionych[rzecz2] += 1
    kolejnosc_ubioru = [rzecz for rzecz in zasady if ile_niespelnionych[rzecz] == 0]
    nr_przegladnanego = 0
    while nr_przegladnanego < len(kolejnosc_ubioru): 
        for ubranie in zasady[kolejnosc_ubioru[nr_przegladnanego]]: 
            ile_niespelnionych[ubranie] -= 1
            if ile_niespelnionych [ubranie] == 0:
                kolejnosc_ubioru.append(ubranie)
        nr_przegladnanego += 1
    if len(kolejnosc_ubioru) != len(zasady): 
        raise Exception('Nie można się ubrać Skurwysynu')
    return kolejnosc_ubioru 

def longest_patch(): 
    N, M = wczytaj_liste()
    lista_krawedzi = []
    for i in range(M): 
        x, y = wczytaj_liste()
        lista_krawedzi.append((x,y))
    listy_krawedzi = zrob_listy_sadziedztwa(lista_krawedzi)
    kolejnosc = wyjscie_do_szkoly_bfs(lista_krawedzi)
    najdluzsze_drogi = {}
    for wierzcholek in kolejnosc: 
        if len(listy_krawedzi[wierzcholek]) == 0: 
            najdluzsze_drogi[wierzcholek] = 0
        else: 
            maksimum = 0 
            for x in listy_krawedzi[wierzcholek]: 
                if najdluzsze_drogi[x]> maksimum:
                      maksimum = najdluzsze_drogi[x]
            najdluzsze_drogi[wierzcholek] = maksimum + 1
    najdluzsza = 0 
    for a_chuj_wie_co in najdluzsze_drogi: 
        if najdluzsze_drogi[a_chuj_wie_co] > najdluzsza:
            najdluzsza = najdluzsze_drogi[a_chuj_wie_co]
    print (najdluzsza)

longest_patch()

Submission status: Accepted

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

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

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

dp = [-1]*(n+1)
dp[0] = 0

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import deque

INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))


def Topological_sorting(g):
    in_deg = [0]*g.N
    for i in range(g.N):        # ２重ループでO(E)
        for to_, _ in g.E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(g.N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  # O(V+E)
        v = deq.popleft()
        for t, _ in g.E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != g.N:
        return False
    return ans


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)

    tsg = Topological_sorting(g)

    DP = [0]*N
    for i in tsg:
        for to, _ in g.E[i]:
            DP[to] = max(DP[i]+1, DP[to])
    print(max(DP))

    return


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:
import sys
sys.setrecursionlimit(10000000)
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]>0:
        return dp[i]
    else:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

_map = {}
for i in range(n):
    _map[i+1] = []

for i in range(m):
    [x1, y1] = map(int, input().split())

    _map[y1].append(x1)

_memo = {}

def lpath(vertex):
    if vertex in _memo:
        return _memo[vertex]

    if len(_map[vertex]) == 0:
        return 0
    else:
        _max = 0
        for nv in _map[vertex]:
            # print(nv)
            x = lpath(nv)
            if (x > _max):
                _max = x

        _memo[vertex] = _max + 1
        return _max + 1

global_longest_path = 0
for i in range(n):
    longest_path_to_cur_node = lpath(i + 1)
    if global_longest_path < longest_path_to_cur_node:
        global_longest_path = longest_path_to_cur_node

print(global_longest_path)

Submission status: Accepted

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

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

graph = [[] for _ in range(N)]
out_deg = [0]*N
for x, y in xy:
    graph[y-1].append(x-1)
    out_deg[x-1] += 1


dp = [0]*N
stack = deque([i for i in range(N) if out_deg[i]==0])
while stack:
    node = stack.popleft()
    for child in graph[node]:
        dp[child] = max(dp[child], dp[node]+1)
        out_deg[child] -= 1
        if out_deg[child] == 0:
            stack.append(child)
    
print(max(dp))

Submission status: Accepted

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


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

tree = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)

set_ = set([])
for i in range(n):
    for j in tree[i]:
        set_.add(j)

start = set([])
for i in range(n):
    if i not in set_:
        start.add(i)

memo = {}
dp = [0]*n

def solve(pos):
    if pos in memo:
        return memo[pos]
    if len(tree[pos]) == 0:
        memo[pos] = 0
        return memo[pos]

    tmp = 0
    for next_pos in tree[pos]:
        tmp = max(solve(next_pos) + 1, tmp)
    memo[pos] = tmp
    return memo[pos]

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

Submission status: Accepted

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

N,M = map(int,input().split())
# edge[i]: 頂点iの出力辺の行き先
edge = [[] for i in range(N)]

#ins[i]: 頂点iの入力辺の数
ins = [0] * N
for i in range(M):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    ins[y-1] += 1

# 入力辺を持たないノードのリスト
outs = deque([V for V in range(N) if ins[V] == 0])

# dp[i]: 頂点iを終点とする最長のパスの長さ
dp = [0] * N

# DFS的にトポロジカルソートしながらDPする
while outs:
    i = outs.pop()
    # 頂点iの行き先である頂点jについて
    # dp[j] = max(dp[j], dp[i]+1)
    for j in edge[i]:
        ins[j] -= 1
        if ins[j] == 0:
            outs.append(j)
        dp[j] = max(dp[j], dp[i]+1)

print(max(dp))

Submission status: Accepted

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

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

dp = [-1 for k in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [0] * (N + 1)
e = dd(list)
inc = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  inc[v] += 1
def topologically(n, e, inc):
  res = []
  s = []
  c = 0
  many = 0
  for i in range(1, n + 1):
    if inc[i] == 0:
      s.append(i)
      c += 1
  many = c > 1
  while len(s):
    p = s.pop()
    res.append(p)
    for q in e[p]:
      inc[q] -= 1
      if inc[q] == 0:
        s.append(q)
    many = many or ((len(s) - c) > 0)
    c = len(s)
  return res + [many]
res = topologically(N, e, inc)
for x in range(N):
  i = res[x]
  for q in e[i]:
    dp[q] = max(dp[q], dp[i] + 1)
print(max(dp))

Submission status: Accepted

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

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

dp = [-1] * N
def dist(vertex):
    if dp[vertex] != -1:
        return dp[vertex]
    
    res = 0
    for to in edges[vertex]:
        res = max(res, dist(to) + 1)
    
    dp[vertex] = res
    return  res

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from collections import defaultdict
d,nbr = defaultdict(list),defaultdict(list)

def topological(inDeg,n,d):
    q,topOrder = [],[]
    vis = [ False for i in range(n+1)]
    for i in range(1,n+1):
        if inDeg[i]==0:
            q.append(i)
            vis[i] = True
    while len(q)>0:
        top = q.pop(0)
        topOrder.append(top)
        for x in d[top]:
            inDeg[x]-=1
            if inDeg[x]==0:
                q.append(x)
                vis[x]=True
    return topOrder


n, m = map(int,stdin.readline().split())
E = []
inDeg = [ 0 for i in range(n+1)]
for i in range(m):
    x,y = map(int,stdin.readline().split())
    E.append([x,y])
    inDeg[y]+=1
    d[x].append(y)

order = topological(inDeg,n,d)
for k,v in zip(d.keys(),d.values()):
    for x in v:
        nbr[x].append(k)
# for k,v in zip(nbr.keys(),nbr.values()):
#     print(k,v)
dp = [ 0 for i in range(n+1) ]
for x in order:
    if len(nbr[x])>0:
        for near in nbr[x]:
            dp[x] = max(dp[x],dp[near]+1)

print(max(dp))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from sys import setrecursionlimit

    setrecursionlimit(10 ** 7)

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

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

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#g-%E5%95%8F%E9%A1%8C---longest-path
    def rec(v):
        if dp[v] != -1:
            return dp[v]

        result = 0

        for next_v in graph[v]:
            result = max(result, rec(next_v) + 1)

        dp[v] = result

        return dp[v]

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def topological_sort(N,lst_ab):
    a_to_b=[[] for i in range(n+1)]
    b_from_a=[0]*(n+1)
    for A,B in lst_ab:
        a_to_b[A].append(B)
        b_from_a[B]+=1
    flag=[0]*(n+1)
    ans=[]
    for i in range(1,n+1):
        if b_from_a[i]==0 and flag[i]==0:
            flag[i]=1
            ans.append(i)
            que=[i]
            while que:
                h=que.pop()
                for u in a_to_b[h]:
                    b_from_a[u]-=1
                    if flag[u]==0 and b_from_a[u]==0:
                        flag[u]=1
                        ans.append(u)
                        que.append(u)
    if len(ans)==N: return ans
    else: return False
n,m=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(m)]
h=topological_sort(n,xy)
data=[[] for i in range(n+1)]
for x,y in xy:
    data[x].append(y)
lst=[0]*(n+1)
for u in h:
    for v in data[u]:
        lst[v]=max(lst[v],lst[u]+1)
print(max(lst))

Submission status: Accepted

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

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

dp = [-1] * N
def dist(v):
  if dp[v] != -1: return dp[v]
  
  res = 0
  for to in edge[v]:
    res = max(res, dist(to) + 1)
  
  dp[v] = res
  return res

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

print(ans)