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:

Solution (Python):


import sys
from collections import defaultdict, deque

INF = 10 ** 5
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()

G = defaultdict(list)
G2 = defaultdict
in_degree = [0] * n
for _ in range(m):
    x, y = LI_()
    G[x].append(y)
    in_degree[y] += 1


q = deque()
for v, e in enumerate(in_degree):
    if e == 0:
        q.append(v)

res = []
while q:
    v = q.popleft()
    res.append(v)
    for nv in G[v]:
        in_degree[nv] -= 1
        if in_degree[nv] == 0:
            q.append(nv)

dp = [0] * n
for v in res:
    for nv in G[v]:
        dp[nv] = max(dp[nv], dp[v] + 1)

print(max(dp))

Solution (Python):
from collections import deque

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

E = [[] for i in range(n+1)]
IN = [0] * (n+1)

for a, b in X:
    E[a].append(b)
    IN[b] += 1

q = deque((i, 0) for i in range(1, n+1) if IN[i] == 0)
D = [0] * (n+1)

while q:
    i, d = q.popleft()
    IN[i] -= 1
    if IN[i] > 0:
        continue
    D[i] = d
    for e in E[i]:
        q.append((e, d+1))

print(max(D))

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

for a, b in X:
    E[a].append(b)

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

def dfs(i):
    if memo[i] != -1:
        return memo[i] + 1
    if not E[i]:
        return 0

    memo[i] = max(dfs(e) for e in E[i])
    return memo[i] + 1

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

Solution (Python):
n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
q=[]
for i in range(n):
    if not oya[i]:
        q.append([i,ko[i]])
while q:
    now,path=q.pop()
    for i in path:
        oya[i].remove(now)
        if not oya[i]:
            q.append([i,ko[i]])
        rank[i]=max(rank[i],rank[now]+1)
print(max(rank))

Solution (Python):
def main(): 
  N, M = list(map(int, input().split()))
  Data = []
  for i in range(M):
    Data.append(list(map(lambda x: int(x) - 1, input().split())))
  Data.sort()
  
  S = [i for i in range(N)]
  Lo = {}
  G = [0 for i in range(N)]
  for i in Data:
    Lo.setdefault(i[0], []).append(i[1])
    G[i[1]] += 1
    S[i[1]] = -1

  S = list(set(S))
  S.sort()
  S.remove(-1)
  
  L = []  
  while S != []:
    t = S.pop(-1)
    L.append(t)
    if t in Lo:
      for i in Lo[t]:
        G[i] -= 1
        if G[i] == 0:
          S.append(i)

  DP = [0 for i in range(N)]
  
  for i in range(N):
    t = L[i]
    if t in Lo:
      for j in Lo[t]:
        DP[j] = max(DP[j], DP[t] + 1)
        
  print(max(DP))
main()

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

global score

def dfs(graph, nd, d):
    global score
    max_depth = 0
    if score[nd] != -1:
        return score[nd] + 1
    if len(graph[nd]) == 0:
        score[nd] = 0
        return 1
    for adj in graph[nd]:
        max_depth = max(max_depth, dfs(graph, adj, d + 1))

    
    score[nd] = max_depth
    return score[nd] + 1


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    sys.setrecursionlimit(100000)
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    global score
    score = {}
    for i in range(1, N+1):
        graph[i] = []
        score[i] = -1
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)

    for i in range(1, N + 1):
        dfs(graph, i, 0)
    max_score = 0
    for i in range(1, N + 1):
        max_score = max(max_score, score[i])
    print max_score






















if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

global score

def dfs(graph, nd, d):
    global score
    max_depth = 0
    if score[nd] != -1:
        return score[nd] + 1
    if len(graph[nd]) == 0:
        score[nd] = 0
        return 1
    for adj in graph[nd]:
        max_depth = max(max_depth, dfs(graph, adj, d + 1))

    
    score[nd] = max_depth
    return score[nd] + 1


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    sys.setrecursionlimit(100000)
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    global score
    score = {}
    for i in range(1, N+1):
        graph[i] = []
        score[i] = -1
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)

    for i in range(1, N + 1):
        dfs(graph, i, 0)
    max_score = 0
    for i in range(1, N + 1):
        max_score = max(max_score, score[i])
    print max_score






















if __name__ == '__main__':
    main()

Solution (Python):

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

N, M = map(int, input().split())
edges = [set() for _ in range(N)]
ins = [0]*N
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    ins[b] += 1
    edges[a].add(b)

dp = [-1]*N


def dfs(s):
    if dp[s] != -1:
        return dp[s]
    mx = 0
    if edges[s]:
        mx = max([dfs(dest)+1 for dest in edges[s]])
    dp[s] = mx
    return mx


ans = -1
for i in range(N):
    ans = max(ans, dfs(i))

print(ans)

Solution (Python):

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

N, M = map(int, input().split())
edges = [set() for _ in range(N)]
ins = [0]*N
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    ins[b] += 1
    edges[a].add(b)

dp = [-1]*N

start = []
for i in range(N):
    if ins[i] == 0:
        start.append(i)


def dfs(s):
    if dp[s] != -1:
        return dp[s]
    mx = 0
    if edges[s]:
        mx = max([dfs(dest)+1 for dest in edges[s]])
    dp[s] = mx
    return mx


ans = -1
for i in range(N):
    if ins[i] == 0:
        ans = max(ans, dfs(i))

print(ans)

Solution (Python):

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

N, M = map(int, input().split())
edges = [set() for _ in range(N)]
ins = [0]*N
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    ins[b] += 1
    edges[a].add(b)

dp = [-1]*N

start = []
for i in range(N):
    if ins[i] == 0:
        start.append(i)


def dfs(s):
    if dp[s] != -1:
        return dp[s]
    mx = 0
    if edges[s]:
        mx = max([dfs(dest)+1 for dest in edges[s]])
    dp[s] = mx
    return mx


ans = max(dfs(i) for i in range(N))
print(ans)

Solution (Python):
N,M=[int(x) for x in raw_input().split()]
A=[[] for i in range(N)]
B=[[] for i in range(N)]
C=[-1 for i in range(N)]
D=[0 for i in range(N)]
E=[0 for i in range(N)]

for i in range(M):
    a,b=[int(x)-1 for x in raw_input().split()]
    A[a].append(b) 
    B[b].append(a) 
F=[]
s=0
for i in range(N):
    D[i]=len(B[i])
    if D[i]==0:
        F.append(i)
        C[i]=0
        for a in A[i]:
            E[a]+=1
        s+=1
level=0
while s<N:
    level+=1
    Fnew=[]
    T=[]
    for f in F:
        for a in A[f]:
            if E[a]==D[a]:
                C[a]=level
                Fnew.append(a)
                s+=1
                E[a]=0
                for aa in A[a]:
                    T.append(aa)
    F=Fnew[:]
    for aa in T:
        E[aa]+=1
print max(C)

Solution (Python):
N, M = map(int, input().split())

E = [[] for _ in range(N)]
rE = [0] * N

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

dp = [0] * N

Q = [x for x in range(N) if not rE[x]]

while Q:
    v = Q.pop()
    memo = dp[v] + 1
    for u in E[v]:
        dp[u] = max(dp[u], memo)
        rE[u] -= 1
        if not rE[u]:
            Q.append(u)

print(max(dp))

Solution (Python):
from collections import deque


def main():
    N, M = map(int, input().split())
    prv = [0] * (N+1)
    nxt = [[] for _ in range(N+1)]
    path = [0] * (N+1)
    for _ in range(M):
        x, y = map(int, input().split())
        prv[y] += 1
        nxt[x].append(y)
    q = deque()
    for i in range(1, N+1):
        if prv[i] == 0:
            q.append(i)
    while len(q):
        cur = q.popleft()
        for adj in nxt[cur]:
            path[adj] = max(path[adj], path[cur] + 1)
            prv[adj] -= 1
            if prv[adj] == 0:
                q.append(adj)
    print(max(path))


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin, setrecursionlimit as lim

lim(100001)

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()

g1 = [[] for i in xrange(n + 1)]
g2 = [[] for i in xrange(n + 1)]
ans1 = [0 for i in xrange(n + 1)]
ans2 = [0 for i in xrange(n + 1)]

for line in inp:
    u, v = map(int, line.strip().split())
    g1[u].append(v)
    g2[v].append(u)

def dfs1(u):
    if ans1[u] != 0: return ans1[u]
    ret = 0
    for v in g1[u]:
        if ans1[v] != 0: ret = max(ret, ans1[v])
        else: ret = max(ret, dfs1(v))
    ret += 1
    ans1[u] = ret
    return ans1[u]

def dfs2(u):
    if ans2[u] != 0: return ans2[u]
    ret = 0
    for v in g2[u]:
        if ans2[v] != 0: ret = max(ret, ans2[v])
        else: ret = max(ret, dfs2(v))
    ret += 1
    ans2[u] = ret
    return ans2[u]

ans = 0
for i in xrange(1, n + 1):
    if ans1[i] == 0: ans = max(ans, dfs1(i))
for i in xrange(1, n + 1):
    if ans2[i] == 0: ans = max(ans, dfs2(i))

print ans - 1

Solution (Python):
n, m = map(int, input().split())
inpath = [0] * n
innode = [[] for i in range(n)]
outnode = [[] for i in range(n)]
dp = [0] * n

for i in range(m):
    x, y = map(lambda z:z-1,map(int, input().split())) 
    innode[y].append(x)
    outnode[x].append(y)
    inpath[y] += 1
S = []
L = []

for i in range(n):
    if inpath[i] == 0:
        S.append(i) 

while S: 
    k = S.pop()
    L.append(k)
    for i in outnode[k]:
        inpath[i] -= 1
        if inpath[i] == 0:
            S.append(i)
 
for i in L:
    if not innode[i]: 
        dp[i] = 0
    else:
        for j in innode[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

Solution (Python):


from Queue import Queue

n, m = map(int, raw_input().split())
indeg = [0] * n
graph = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, raw_input().split())
    graph[x - 1].append(y - 1)
    indeg[y - 1] += 1

cola = Queue()
for i in range(n):
    if indeg[i] == 0:
        cola.put(i)
topsort = []
while not cola.empty():
    v = cola.get()
    topsort.append(v)
    for i in graph[v]:
        indeg[i] -= 1
        if indeg[i] == 0:
            cola.put(i)

dp = [0] * n
for i in range(n - 1, -1, -1):
    v = topsort[i]
    for u in graph[v]:
        dp[v] = max(dp[v], 1 + dp[u])
print(max(dp))

Solution (Python):
n, m = map(int, input().split())
dp=[0]*(n+1)
e=[ set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    e[a].add(b)
    dp[b]+=1

q=[0]*(n+1)
j=0
for z in range(len(dp)):
    if dp[z]==0:
        q[j]=z
        j=j+1
color=0
i=1
while i<j:
    end=j
    for qel in range(i, end):
        for w in e[q[qel]]:
            dp[w]-=1
            if dp[w]==0: 
                q[j]=w
                j=j+1
    i=end
    color=color+1

print(color-1)

Solution (Python):
import sys

N, M = map(int, input().split())
EdgeTo = [[] for _ in range(N)]
sys.setrecursionlimit(N+M)

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


DP = [-1] * N
def From(i):
    if DP[i] != -1: return DP[i]
    else:
        maxLength = 0
        if not EdgeTo[i]:
            DP[i] = maxLength
        else:
            for node in EdgeTo[i]:
                maxLength = max(maxLength, 1 + From(node))
            DP[i] = maxLength
        return maxLength

Ans = 0
for i in range(N):
    Ans = max(Ans, From(i))
print(Ans)

Solution (Python):
from sys import setrecursionlimit; setrecursionlimit(10**9)
N, M = map(int, input().split())
edge = {i:[] for i in range(1, N+1)}
starts = set(i for i in range(1, N+1))
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    starts -= {y}

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

def rec(e):
    if memo[e] != -1:
        return memo[e]
    ret = 0
    for f in edge[e]:
        ret = max(ret, rec(f) + 1)
    memo[e] = ret
    return ret

max_d = 0
for s in starts:
    max_d = max(max_d, rec(s))
print(max_d)

Solution (Python):
"""
https://atcoder.jp/contests/dp/tasks/dp_g

Using list to store adjacent list is faster than using sets.
Maybe it is because the append operation of list in python is faster than add operation of sets.

Using defaultdict instead of list to store adj is faster. Maybe it is because in case the graph is
sparse, defauldict can save more query time.
"""
from sys import stdin
from collections import defaultdict, deque
input = stdin.readline
N, M = map(int, input().split())
d = [0] * (N + 1)
adj = defaultdict(list)
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    d[y] += 1

dp = [0] * (N + 1)  

Q = deque([i for i in range(1, N + 1) if d[i] == 0])

while Q:
    cur = Q.popleft()
    for nxt in adj[cur]:
        dp[nxt] = max(dp[nxt], dp[cur] + 1)
        d[nxt] -= 1
        if d[nxt] == 0:
            Q.append(nxt)
print(max(dp))

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import defaultdict
input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())

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

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


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import defaultdict
input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())

adj = defaultdict(set)
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].add(y)
    

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


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))

Solution (Python):
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())

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

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


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))

Solution (Python):
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)
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] * (N + 1)


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(200000)
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] * (N + 1)


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

IN = lambda:map(int, input().split())

n, m = IN()
parents = set(range(n + 1))
links = [set() for _ in range(n + 1)]

@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0
  
for _ in range(m):
    x, y = IN()
    parents.discard(y)
    links[x].add(y)

print(max(map(dfs, parents)))

Solution (Python):

N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    
    for p in l:
        
        for c in childs_list[p]:
            costs[c] = max(costs[p]+1, costs[c])
            childs[c] -= 1
            if childs[c] == 0:
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))

Solution (Python):


"""
・自力AC
・トポロジカルソート
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def topological_sort(N, dag):
    
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(dag)):
        
        incnts[dag[i][1]] += 1
        
        outnodes[dag[i][0]].append(dag[i][1])
    
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    
    L = []
    
    while S:
        
        L.append(S.pop())
        
        for node in outnodes[L[-1]]:
            
            incnts[node] -= 1
            
            if incnts[node] == 0:
                S.add(node)
    return L

N, M = MAP()
nodes = [[] for i in range(N)]
edges = [None] * M
for i in range(M):
    x, y = MAP()
    nodes[x-1].append(y-1)
    edges[i] = ((x-1, y-1))


l = topological_sort(N, edges)

ans = [0] * N
for src in l:
    for dest in nodes[src]:
        ans[dest] = max(ans[dest], ans[src]+1)
print(max(ans))

Solution (Python):


"""
参考：https://qiita.com/drken/items/03c7db44ccd27820ea0d
・メモ化再帰でもやってみる。
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
nodes = [[] for i in range(N)]
edges = [None] * M
for i in range(M):
    x, y = MAP()
    nodes[x-1].append(y-1)
    edges[i] = ((x-1, y-1))

memo = [-1] * N

def dfs(cur):
    if memo[cur] != -1:
        return memo[cur]
    mx = 0
    for dest in nodes[cur]:
        mx = max(mx, dfs(dest)+1)
    memo[cur] = mx
    return mx

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

Solution (Python):


"""
参考：https://qiita.com/drken/items/03c7db44ccd27820ea0d
・自力AC
・トポロジカルソート
・解説読んで、DPする位置をちょっと変えてみた。
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def topological_sort(N, dag):
    
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(dag)):
        
        incnts[dag[i][1]] += 1
        
        outnodes[dag[i][0]].append(dag[i][1])
    
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    
    L = []
    
    while S:
        
        L.append(S.pop())
        
        for node in outnodes[L[-1]]:
            
            incnts[node] -= 1
            
            if incnts[node] == 0:
                S.add(node)

        
        src = L[-1]
        for dest in nodes[src]:
            dp[dest] = max(dp[dest], dp[src]+1)
    return L

N, M = MAP()
nodes = [[] for i in range(N)]
edges = [None] * M
for i in range(M):
    x, y = MAP()
    nodes[x-1].append(y-1)
    edges[i] = ((x-1, y-1))

dp = [0] * N

l = topological_sort(N, edges)

print(max(dp))

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def topological_sort(N, dag):
    
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(dag)):
        
        incnts[dag[i][1]] += 1
        
        outnodes[dag[i][0]].append(dag[i][1])
    
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    
    L = []
    
    while S:
        
        L.append(S.pop())
        
        for node in outnodes[L[-1]]:
            
            incnts[node] -= 1
            
            if incnts[node] == 0:
                S.add(node)
    return L

N, M = MAP()
nodes = [[] for i in range(N)]
edges = [None] * M
for i in range(M):
    x, y = MAP()
    nodes[x-1].append(y-1)
    edges[i] = ((x-1, y-1))


l = topological_sort(N, edges)

ans = [0] * N
for src in l:
    for dest in nodes[src]:
        ans[dest] = max(ans[dest], ans[src]+1)
print(max(ans))

Solution (Python):
from collections import defaultdict,deque
v,n=map(int,input().split())
es=[[int(x)for x in input().split()]for _ in range(n)]
outs=defaultdict(list)
ins=defaultdict(int)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2]+=1
q=deque(v1 for v1 in range(v+1)if ins[v1]==0)
res=[]
p=[0]*-~v
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
            p[v2]=v1
dp=[0]*-~v
for i in res[1:]:
  dp[i]=dp[p[i]]+1
print(max(dp)-1)

Solution (Python):
from collections import defaultdict,deque
v,n=map(int,input().split())
es=[[int(x)for x in input().split()]for _ in range(n)]
outs=defaultdict(list)
ins=defaultdict(int)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2]+=1
q=deque(v1 for v1 in range(v+1)if ins[v1]==0)
res=[]
p=[0]*-~v
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
            p[v2]=v1
dp=[0]*-~v
for i in res[1:]:
  dp[i]=dp[p[i]]+1
print(max(dp)-1)

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

N,M=map(int, sys.stdin.readline().split())

nl=[ [] for i in range(N+1) ] 

for i in range(M):
	x,y=map(int, raw_input().split())
	nl[x].append(y)


memo={}

def depth(n):
	if n in memo: return memo[n]
	ret=0
	if len( nl[n] )==0:
		return 0
	else:
		for x in nl[n]:
			ret=max(ret, depth(x)+1)
	memo[n]=ret
	return ret


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

print ans

Solution (Python):
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))

Solution (Python):

"""
Created on Sat Jan 19 16:05:26 2019
DP_G
@author: maezawa
"""
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
v = [-1]*(n+1)
adj = [[] for _ in range(n+1)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    adj[i].append(j)
    
def dfs(vi):
    if v[vi] != -1:
        return v[vi]
    res = 0
    for nb in adj[vi]:
        res0 = dfs(nb) +1
        if res < res0:
            res = res0
    v[vi] = res
    return res

ans = 0
for node in range(1, n+1):
    current = dfs(node)
    if current > ans:
        ans = current
print(ans)

Solution (Python):

"""
Created on Sat Jan 19 16:05:26 2019
DP_G
@author: maezawa
"""
import sys
sys.setrecursionlimit(10**6)

n, m = list(map(int, input().split()))
v = [-1]*(n+1)
adj = [[] for _ in range(n+1)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    adj[i].append(j)
    
def dfs(vi):
    if v[vi] != -1:
        return v[vi]
    res = 0
    for nb in adj[vi]:
        res0 = dfs(nb) +1
        if res < res0:
            res = res0
    v[vi] = res
    return res

ans = 0
for node in range(1, n+1):
    current = dfs(node)
    if current > ans:
        ans = current
print(ans)

Solution (Python):

"""
Created on Sat Jan 19 16:05:26 2019
DP_G
@author: maezawa
"""
import sys
sys.setrecursionlimit(10**5)

n, m = list(map(int, input().split()))
v = [-1]*(n+1)
adj = [[] for _ in range(n+1)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    adj[i].append(j)
    
def dfs(vi):
    if v[vi] != -1:
        return v[vi]
    res = 0
    for nb in adj[vi]:
        res0 = dfs(nb) +1
        if res < res0:
            res = res0
    v[vi] = res
    return res

ans = 0
for node in range(1, n+1):
    current = dfs(node)
    if current > ans:
        ans = current
print(ans)

Solution (Python):

"""
Created on Sat Jan 19 16:05:26 2019
DP_G
@author: maezawa
"""
import sys
sys.setrecursionlimit(10**5)

n, m = list(map(int, input().split()))
v = [-1]*(n+1)
adj = [[] for _ in range(n+1)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    adj[i].append(j)
    
def dfs(vi):
    if v[vi] != -1:
        return v[vi]
    res = 0
    for nb in adj[vi]:
        res0 = dfs(nb) +1
        if res < res0:
            res = res0
    v[vi] = res
    return res

ans = 0
for node in range(1, n+1):
    current = dfs(node)
    if current > ans:
        ans = current
print(ans)