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

Submission status: Accepted

Solution code:
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))

    #if max_depth > score[nd]:
    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
##        q = [i]
##        d = 0
##        while 1:
##            if len(q) <= 0:
##                score[i] = d
##                break
##            nd = q.pop()
##            if score[nd] != -1:
##                score[i] = d + score[nd]
##                break
##            for adj in graph[nd]:
##                if score[nd] + 1 > score[adj]:
##                    q.append(adj)
##                    score[adj] = score[nd] + 1
##                else:







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# python template for atcoder1
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)

Submission status: Accepted

Solution code:
# python template for atcoder1
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)

Submission status: Accepted

Solution code:
# python template for atcoder1
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)

Submission status: Accepted

Solution code:
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) #to
    B[b].append(a) #from
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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())) # 添え字を1~nから0~n-1に調整
    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) #流入パスがないノードをSに追加

while S: # 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))

Submission status: Accepted

Solution code:


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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
"""
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)  # dp denotes longest path ends at i

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))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict
input = stdin.readline
setrecursionlimit(200000)
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 = [-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)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict
input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = defaultdict(set)
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].add(y)
    # d[y] += 1

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)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [set() for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].add(y)
    # d[y] += 1

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)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

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)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
# input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/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 = []
    # p = l.pop()
    for p in l:
        # cnt = costs[p]
        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))

Submission status: Accepted

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

"""
・自力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])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            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))

Submission status: Accepted

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

"""
参考：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):
    # メモはグローバルに持っているので、
    # 全ノードについてdfsしても無駄に潜ることはない。
    ans = max(ans, dfs(i))
print(ans)

Submission status: Accepted

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

"""
参考：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])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            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))

Submission status: Accepted

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

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])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

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:
# -*- coding: utf-8 -*-
"""
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = collections.defaultdict(set)
    for _ in range(m):
        x,y = LI()
        e[y].add(x)

    fm = {}
    def f(i):
        if i in fm:
            return fm[i]
        if len(e[i]) == 0:
            fm[i] = 0
            return 0
        r = 0
        for c in e[i]:
            t = f(c)
            if r < t:
                r = t
        fm[i] = r + 1
        return r + 1

    r = 0
    for i in range(1,n+1):
        t = f(i)
        if r < t:
            r = t

    return r


print(main())

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def rec(vv):
    if p[vv] >= 0:
        return p[vv]

    res = 0
    for nv in g[vv]:
        res = max(res, rec(nv) + 1)
    p[vv] = res
    return res


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

for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    g[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)


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

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


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

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

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
X = [[] for i in range(N)] # iからの行き先
Y = [0 for i in range(N)] # iに来る辺の数
dp = [0 for i in range(N)] # iで終わる最長経路の長さ

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


Q = deque([])
for i in range(N):
    if Y[i] == 0:
        Q.append(i)

while len(Q) > 0:
    i = Q.popleft()
    for x in X[i]:
        dp[x] = max(dp[x], dp[i] + 1)
        Y[x] -= 1
        if Y[x] == 0:
            Q.append(x)

print(max(dp))