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 collections
import sys
def main():

    sys.setrecursionlimit(10 ** 6)

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

    memo = dict()
    def helper(node):
        if node in memo:
            return memo[node]

        max_l = 0
        for nxt in graph[node]:
            max_l = max(max_l, helper(nxt) + 1)
        memo[node] = max_l
        return max_l

    max_l = 0
    for i in range(1, N+1):
        l = helper(i)
        max_l = max(max_l, l)
    return max_l

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import deque
 
N, M = map(int, input().split())
adjL = [[] for v in range(N)]
indegs = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    adjL[x-1].append(y-1)
    indegs[y-1] += 1
 
dp = [0] * N
Q = deque([v for v in range(N) if indegs[v] == 0])
while Q:
    vNow = Q.popleft()
    for v2 in adjL[vNow]:
        dp[v2] = max(dp[v2], dp[vNow] + 1)
        indegs[v2] -= 1
        if indegs[v2] == 0:
            Q.append(v2)
 
print(max(dp))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    n, m = map(int, input().split())
    e = [[]for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        e[a].append(b)

    dp = [-1 for i in range(n)]
    def f(i):
        if dp[i] != -1:
            return dp[i]
        ret = 0
        for v in e[i]:
            ret = max(ret, f(v) + 1)
        dp[i] = ret
        return dp[i]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    n, m = map(int, input().split())
    e = [[]for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        e[a].append(b)

    dp = [-1 for i in range(n)]
    vis = [False for i in range(n)]

    def f(i):
        if vis[i]:
            return dp[i]
        ret = 0
        for v in e[i]:
            ret = max(ret, f(v) + 1)
        vis[i] = True
        dp[i] = ret
        return dp[i]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = ""; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def inp(): return int(sys.stdin.readline())
def st(): return input()
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]

def main():
    n, m = wi()
    xy = mip(m)
    direct = [[] for _ in range(n)]
    for x, y in xy:
        direct[x].append(y)
    flag = [0 for _ in range(n)]
    """f(x)=(xを始点とする最長経路)とすると
    f(x)=
    {0 (xが葉のとき)
    max{f(y)+1|xからyへの辺があるようなy (そうでないとき)}
    として再帰で計算できるよ。答えはmax{f(x)}だね。
    再帰の深さがO(N)くらいになる
    """
    dp = [0 for _ in range(n)]
    def f(x):
        if flag[x]:
            return dp[x]
        flag[x] = 1
        fans = 0
        for y in direct[x]:
            fans = max(fans, f(y) + 1)
        dp[x] = fans
        return dp[x]

    ans = []
    for i in range(n):
        ans.append(f(i))
    print(max(ans))
    # 計算量はO(N+M)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N,M = map(int,input().split())
graph = [[] for i in range(10**5 + 10)]
dp = [-1 for i in range(10**5 + 10)]

for i in range(M):
    x,y = map(int,input().split())
    graph[x-1].append(y-1)
    
def rec(v):
    if dp[v] != -1:
        return dp[v]
    tmp = 0
    for x in graph[v]:
        r = rec(x)+1
        if tmp < r:
            tmp = r
    dp[v] = tmp
    return dp[v]

result = 0
for i in range(N):
    r = rec(i)
    result = r if r>result else result
print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

def tpsort(es, ordered = False):
    n = len(es)
    indgr = [0] * n
    for e in es:
        for u in e:
            indgr[u] += 1
    if ordered:
        from heapq import heappop, heappush
        st = []
        for v in range(n):
            if indgr[v] == 0: heappush(st, v)
        ret = []
        while st:
            v = heappop(st)
            ret.append(v)
            for u in es[v]:
                indgr[u] -= 1
                if indgr[u] == 0: heappush(st, u)
    else:
        st = [v for v in range(n) if indgr[v] == 0]
        ret = []
        while st:
            v = st.pop()
            ret.append(v)
            for u in es[v]:
                indgr[u] -= 1
                if indgr[u] == 0: st.append(u)
    if len(ret) == n:
        return ret
    else:
        return False

N, M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    x, y = map(lambda x: int(x)-1, input().split())
    es[x].append(y)
tplst = tpsort(es)
dp = [0] * N
for v in tplst:
    for u in es[v]:
        dp[u] = max(dp[u], dp[v]+1)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]

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

    maxLeng = [-1] * N

    def search(now):
        if maxLeng[now] != -1:
            return maxLeng[now]

        ret = 0
        for to in edge[now]:
            ret = max(ret, search(to))

        maxLeng[now] = ret + 1
        return ret + 1

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

    print(ans - 1)

sol()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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

root = [[] for _ in range(n)]

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

memo = ["empty" for _ in range(n)]

def dp(x):
    if memo[x] == "empty":
        res = 0
        for i in root[x]:
            res = max(res, dp(i)+1)
        memo[x] = res

    return memo[x]

for j in range(n):
    dp(j)

print(max(memo))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2147483647)

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

def solve(n, m):
    graph = dict()
    table = [None]*n

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

    # print(graph)

    # 頂点iからの先のグラフの、最大pathの大きさを返す
    def dp(i):
        # print('b', i, table)
        if table[i]:
            return table[i]

        childs = graph.get(i)
        if not childs:
            table[i] = 0
        else:
            table[i] = max([dp(y) for y in childs]) + 1

        # print('a', i, table)
        return table[i]

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

    return max(filter(lambda x: x, table))

print(solve(n, m))

"""
"""

Submission status: Accepted

Solution code:
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 100
import sys
sys.setrecursionlimit(1000000)

adj=[]
n,m = map(int,raw_input().split())
for i in range(n+1):
	adj.append([])
dp=[0]*(n+1)	
def dd(l):
	if(dp[l]!=-1):
		return dp[l]
	ma=dd(adj[l][0])
	for j in range(1,len(adj[l])):
		ma=max(ma,dd(adj[l][j]))
	dp[l]=ma+1
	return ma+1	
for i in range(m):
	x,y = map(int,raw_input().split())
	adj[y].append(x)
	dp[y]=-1
ans=[]
for i in range(1,n+1):
	ans.append(dd(i))
	# print i
print max(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


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

G = {k: [] for k in range(N)}
for _ in range(M):
    x, y = map(int, input().split())

    # 有向グラフ
    G[x-1].append(y-1)  # 0-indexed

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


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

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

    return dp[v]


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(524287)

n,m,*l = map(int,open(0).read().split())
pas = [[] for _ in range(n)]
for x,y in zip(l[::2],l[1::2]):
	pas[x-1].append(y-1)

INF = float("inf")
done = [-INF]*n

def dfs(t):
	if done[t] >= 0:
		pass
	elif pas[t]:
		done[t] = max(dfs(s) for s in pas[t]) + 1
	else:
		done[t] = 0
	return done[t]

print(max(dfs(i) for i in range(n)))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(524287)

n,m,*l = map(int,open(0).read().split())
pas = [[] for _ in range(n)]
for x,y in zip(l[::2],l[1::2]):
	pas[x-1].append(y-1)

INF = float("inf")
done = [-INF]*n

@lru_cache(maxsize = None)
def dfs(t):
	if done[t] >= 0:
		pass
	elif pas[t]:
		done[t] = max(dfs(s) for s in pas[t]) + 1
	else:
		done[t] = 0
	return done[t]

print(max(dfs(i) for i in range(n)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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 = [None] * (N+1)

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if graph[x]:
        dp[x] = 1 + max(dfs(y) for y in graph[x])
    else:
        dp[x] = 0
    return dp[x]

answer = max(dfs(x) for x in range(1,N+1))

print(answer)