Problem:


Score : 100 points

Problem Statement

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq x_i, y_i \leq N

All pairs (x_i, y_i) are distinct.

G does not contain directed cycles.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the length of the longest directed path in G.

Sample Input 1

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

Sample Output 1

3

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

Sample Input 2

6 3
2 3
4 5
5 6

Sample Output 2

2

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

Sample Input 3

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

Sample Output 3

3

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



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


Sample output:
3

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G
# CreatedDate:  2020-05-18 17:21:29 +0900
# LastModified: 2020-05-19 01:07:59 +0900
#


import os
import sys
from collections import deque
#import numpy as np
#import pandas as pd
def chmax(s,t):
    if s<t:
        return t
    else:
        return s


def longest_path(ans_list,node_list,lon_path):
    while ans_list:
        u = ans_list.pop()
        for v,_from in enumerate(node_list):
            if u in _from and lon_path[v]<lon_path[u]+1:
                lon_path[v]=lon_path[u]+1
    print(max(lon_path))

def main():
    n,m = map(int,input().split())
    node_list = [[] for _ in range(n+1)]
    to_count = [0]*(n+1)
    for _ in range(m):
        s,t = map(int,input().split())
        node_list[s].append(t)
        to_count[t]+=1
    q = deque()
    for i,x in enumerate(to_count):
        if x==0:
            q.append(i)
    q.popleft()
    distance = [0]*(n+1)
    ans_list = []
    while q:
        u = q.popleft()
        for v in node_list[u]:
            to_count[v]-=1
            if to_count[v]==0:
                q.append(v)
                distance[v]=chmax(distance[v],distance[u]+1)
        ans_list.append(u)
    print(max(distance))
#    longest_path(ans_list,node_list,lon_path)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import collections

# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    return b

def main():
    # 入力
    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())
        # 最初のindexをゼロにする
        lst_edge[x-1].append(y-1)
        deg[y-1] += 1

    # 入力辺を持たない頂点をqueueに入れる
    que = collections.deque()
    for v in range(N):
        if deg[v] == 0:
            que.append(v)

    # 各頂点の最初に入力辺を持たなかった点からの距離
    dp = [0] * N

    # For sequences, (strings, lists, tuples), use the fact that empty sequences are false.
    # https://www.python.org/dev/peps/pep-0008/#programming-recommendations
    while que:
        v = que.popleft()
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            # エッジ(v, nv)をグラフから削除する
            deg[nv] -= 1
            if deg[nv] == 0:
                # エッジがなくなったことで、入力辺がなくなったらqueueに入れる
                que.append(nv)
                # 最初に入力辺を持たなかった点からの距離
                dp[nv] = chmax(dp[nv], dp[v] + 1)

    print(max(dp))

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def rec(i, dp, nodes):
    # 更新済みのデータの場合はそのまま返す
    if dp[i] != -1:
        return dp[i]

    res = 0
    for next in nodes[i]:
        res = max(res, rec(next, dp, nodes) + 1)
    dp[i] = res
    return res

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, M = map(int, input().rstrip().split())
    nodes = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().rstrip().split())
        nodes[x-1].append(y-1)

    # dp[i] = i番目のノードを始点としたときの最大パス長
    dp = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, rec(i, dp, nodes))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##########################################################
import threading
sys.setrecursionlimit(10**5)
threading.stack_size(10**8)
def dfs(x):
    global l,adj,v
    if v[x]==1:
        return(l[x])
    v[x]=1
    c=0
    for i in adj[x]:
        c=max(c,dfs(i)+1)
    l[x]=c
    return c
def main():
    global l,adj,v
    n,m=map(int,input().split())
    l=[0]*(n+1)
    v=[0]*(n+1)
    adj=[]
    for i in range(n+1):
        adj.append([])
    for i in range(m):
        x,y=map(int,input().split())
        adj[x].append(y)
    ans=0
    for i in range(1,n+1):
        if not v[i]:
            ans=max(ans,dfs(i))
    print(ans)
t=threading.Thread(target=main)
t.start()
t.join()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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



def rec(v):
    if dp[v] != -1:
        return dp[v]
    
    res = 0
    for i in g[v]:
        res = max(res, rec(i) + 1)
    
    dp[v] = res
    return dp[v]

for i in range(n):
    rec(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    g = defaultdict(lambda: [])
    for _ in range(M):
        x, y = geta(int)
        g[x].append(y)

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

    def dfs(i):
        if dp[i] == -1:
            dist = 0
            for j in g[i]:
                dist_j = 1 + dfs(j)
                if dist_j > dist: dist = dist_j
            dp[i] = dist
        return dp[i]

    ans = 0
    for i in range(1, N + 1):
        tmp = dfs(i)
        if tmp > ans: ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

in_cnt = defaultdict(int)
outs = defaultdict(list)
for x,y in edge:
    in_cnt[y-1]+= 1
    outs[x-1].append(y-1)

res = []
queue = deque([i for i in range(n) if in_cnt[i] == 0])

while  len(queue)> 0:
    node = queue.popleft()
    res.append(node)
    for next_node in outs[node]:
        in_cnt[next_node] -= 1
        if in_cnt[next_node] == 0:
            queue.append(next_node)

dp = [0]*n

for i in range(n):
    for nv in outs[res[i]]:
        dp[nv] =max(dp[nv],dp[res[i]] + 1)
print(max(dp))

Submission status: Accepted

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

longs = []
edges = {}
def graph_DP(node_to):
    global longs
    if longs[node_to] != -1:
        return longs[node_to]
    else:
        nodes_next = edges[node_to]
        if not nodes_next:
            longs[node_to] = 0
            return 0
        else:
            long_max_t = 0
            for node_next in nodes_next:
                if longs[node_next] != -1:
                    long_max_t = max(long_max_t, longs[node_next] + 1)
                else:
                    long_max_t = max(long_max_t, graph_DP(node_next) + 1)
            longs[node_to] = long_max_t
            return long_max_t

def main():
    global longs, edges
    n, m = map(int, input().split())
    edges = {e:set() for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].add(g)
    longs = [-1] * (n + 1)

    for i1 in range(1, n + 1):
        if longs[i1] == -1:
            graph_DP(i1)
    print(max(longs))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

longs = []
edges = {}
def graph_DP(node_to, long):
    global longs
    if longs[node_to] != -1:
        return longs[node_to]
    else:
        nodes_next = edges[node_to]
        if not nodes_next:
            longs[node_to] = 0
            return 0
        else:
            long_max_t = 0
            for node_next in nodes_next:
                if longs[node_next] != -1:
                    long_max_t = max(long_max_t, longs[node_next] + 1)
                else:
                    long_max_t = max(long_max_t, graph_DP(node_next, 0) + 1)
            longs[node_to] = long_max_t
            return long_max_t

def main():
    global longs, edges
    n, m = map(int, input().split())
    edges = {e:set() for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].add(g)
    longs = [-1] * (n + 1)

    for i1 in range(1, n + 1):
        if longs[i1] == -1:
            graph_DP(i1, 0)
    print(max(longs))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


d = [0] * n

def dfs(v,edge):
    depth = 0
    for next_v in edge[v]:
        if d[next_v] == 0:
            depth = max(depth,dfs(next_v,edge))
        depth = max(depth,d[next_v])
    depth += 1 
    d[v] = depth
    return depth

for i in range(n):
    dfs(i,edge)
print(max(d)-1)

Submission status: Accepted

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

sys.setrecursionlimit(10**9)


def dfs(v, graph, memo):
    if v in memo:
        return memo[v]

    if graph[v]:
        res = float("-inf")
        for child in graph[v]:
            res = max(res, dfs(child, graph, memo) + 1)
        memo[v] = res
    else:
        res = 0
        memo[v] = 0

    return memo[v]


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

    memo = {}

    res = float("-inf")
    for i in range(N):
        res = max(res, dfs(i, graph, memo))
    print(res)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(11000)
def util(adj, curr, dp):
    res = 0
    if dp[curr] != -1:
        return dp[curr]
    for next in adj[curr]:
        res = max(res,1 + util(adj, next, dp))
    dp[curr] = res
    return res
 
n, m = map(int, input().strip().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().strip().split())
    adj[x - 1].append(y - 1)
dp = [-1]*n
lp = 0
for i in range(n):
    lp = max(lp, util(adj, i, dp))
print(lp)

Submission status: Accepted

Solution code:
from collections import deque

def solve(N, M, graph):

	indegree = {n: 0 for n in range(1, N + 1)}
	for node in graph:
		for nei in graph[node]:
			indegree[nei] += 1

	queue = deque()
	for node in graph:
		if indegree[node] == 0:
			queue.append(node)

	lengths = [0] * (N + 1)

	while queue:
		node = queue.popleft()

		for nei in graph[node]:
			indegree[nei] -= 1

			if indegree[nei] == 0:
				queue.append(nei)

			lengths[nei] = max(lengths[nei], lengths[node] + 1)

	return max(lengths)


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

print(solve(N, M, graph))

Submission status: Accepted

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


def dfs(node, graph, dist, visited):
    if visited[node] == True:
        return dist[node]
    visited[node] = True
    for child in graph[node]:
        dist[node] = max(dist[node], 1+dfs(child, graph, dist, visited))
    return dist[node]


def main():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
    dist = [0]*(n+1)
    visited = [False]*(n+1)
    for node in range(1, n+1):
        if not visited[node]:
            dfs(node, graph, dist, visited)
    print(max(dist))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
dp = [-1]*(n+1)
path = [[] for i in range(n)]
X = []; Y = []
for i in range(m):
    x, y = map(int, input().split())
    X.append(x-1); Y.append(y-1)
    path[x-1].append(y-1)

def dfs(i):
    if dp[i]>0: return dp[i]
    res = 0
    for k in path[i]:
        res = max(res, dfs(k)+1)
    dp[i] = res
    return res

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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, m = IN()
	#s = input()
	nokori = [0]*n
	max_path_from = [0]*n
	path = []
	tl = [[] for _ in range(n)]
	for _ in range(m):
		f, t = IN()
		f,t=f-1, t-1
		path.append((f,t))
		nokori[t] += 1
		tl[f].append(t)
	sl=[i for i, v in enumerate(nokori) if v == 0]
	mp=0
	while len(sl) > 0:
		next_l = []
		for v in sl:
			for t in tl[v]:
				nokori[t] -= 1
				if nokori[t] == 0:
					next_l.append(t)
		sl = next_l
		mp+=1
	print(mp-1)
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]
    indeg = [0] * n
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        E[u].append(v)
        indeg[v] += 1

    # topological sort
    stack = [v for v in range(n) if indeg[v] == 0]
    order = []
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in E[v]:
            indeg[nv] -= 1
            if indeg[nv] == 0:
                stack.append(nv)

    dp = [0] * n
    for v in order[::-1]:
        for nv in E[v]:
            dp[v] = max(dp[v], 1 + dp[nv])

    print(max(dp))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x-1].append(y-1)
dp = [-1]*(n)
 
def dfs(i):
    if dp[i] != -1:
        return dp[i]
    else:
        res = 0
        for j in graph[i]:
            res = max(res,dfs(j)+1)
        dp[i] = res
        return dp[i]
 
for i in range(n):  
    dfs(i)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque


class TPSort:
    """
    トポロジカルソート
    # https://csacademy.com/lesson/topological_sorting/

    # 入次数0のノードから確定し, そのノードから伸びるエッジを削除. を繰り返すことによって DAGのソートをする
    """

    def __init__(self, N):
        self.N = N
        self.indegree = [0] * N  # 入次数
        self.length = [0] * N
        self.edges = [[] for _ in range(N)]

    def add_edge(self, a, b):
        self.edges[a].append(b)
        self.indegree[b] += 1

    def sort(self):
        que = deque([i for i in range(self.N) if self.indegree[i] == 0])

        res = []
        while que:
            n = que.popleft()
            res.append(n)
            for next_n in self.edges[n]:
                self.length[next_n] = max(self.length[next_n], self.length[n] + 1)
                self.indegree[next_n] = self.indegree[next_n] - 1  # 枝刈り
                if self.indegree[next_n] == 0:  # 入次数0なら queue に追加
                    que.append(next_n)
        return res


if __name__ == '__main__':
    n, m = [int(_) for _ in input().split()]
    tp = TPSort(n + 1)

    for i in range(m):
        tp.add_edge(*[int(_) for _ in input().split()])

    tp.sort()
    print(max(tp.length))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r


for i in range(N):
    long(i)
print(max(Far))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(M)]
def tsort(N,E):
    c=[[] for i in range(N)]
    t=[0]*N
    for i,j in E:
        c[i].append(j)
        t[j]+=1
    A,B=zip(*E)
    s=set(range(N))-set(B)
    l=[]
    while s:
        n=s.pop()
        l.append(n)
        for i in c[n]:
            t[i]-=1
            if t[i]==0:
                s.add(i)
    return c,l
c,l=tsort(N,[(x-1,y-1) for x,y in XY])
d=[0]*N
for i in l:
    for n in c[i]:
        d[n]=max(d[n],d[i]+1)
print(max(d))

Submission status: Accepted

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


def longdist(p, dp_l, out_l):
    if len(out_l[p]) == 0:
        return 0
    for q in out_l[p]:
        if dp_l[q] == -1:
            dp_l[q] = longdist(q, dp_l, out_l)
        dp_l[p] = max(dp_l[p], dp_l[q]+1)
    return dp_l[p]


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

input, output = [[] for _ in range(n)], [[] for _ in range(n)]
for x, y in xy:
    input[y - 1].append(x - 1)
    output[x - 1].append(y - 1)

dp = [-1] * n
for i in range(n):
    if dp[i] == -1:
        dp[i] = longdist(i, dp, output)

print(max(dp))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 14:09:04 2020

@author: Kanaru Sato
"""

import sys
sys.setrecursionlimit(10**9)

n,m = list(map(int, input().split()))
thisconnected = [[] for i in range(n+1)]
thismemo = [-1 for i in range(n+1)]

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

def lp(k,memo,connected):
    if memo[k] != -1:
        return memo[k]
    elif not connected[k]:
        memo[k] = 0
        return 0
    else:
        res = -1
        for point in connected[k]:
            if res < lp(point,memo,connected):
                res = lp(point,memo,connected)
        memo[k] = res+1
        return res+1

for i in range(1,n+1):
    if thismemo[i] == -1:
        thismemo[i] = lp(i,thismemo,thisconnected)

print(max(thismemo))

Submission status: Accepted

Solution code:
'''
N頂点M辺の有向グラフGの有向パスのうち最長のものを求めよ。
terms:
    2<=N<=10**5
    1<=M<=10**5
    (x_i,y_i)はすべて相異なる
    Gは有向閉路を含まない

input:
    4 5
    1 2
    1 3
    3 2
    2 4
    3 4
output:
    3
'''


from collections import defaultdict,deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m = inpl()
v = [[] for _ in range(n)]
for i in range(m):
    a, b = inpl()
    v[a - 1].append(b - 1)
'''
v[0]=[1,2]
v[1]=[3]
v[2]=[1,3]
'''

from functools import lru_cache
@lru_cache(maxsize=None)
def dp(x):
    r = 0
    for i in v[x]:
        r = max(r, dp(i) + 1)
    return r

res = max([dp(i) for i in range(n)])
print(res)

Submission status: Accepted

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

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

memo = [-1] * n

def dp(x):
	if memo[x] != -1:
		return memo[x]
	r = 0
	for i in v[x]:
		r = max(r, dp(i) + 1)
	memo[x] = r
	return r

res = max([dp(i) for i in range(n)])
print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[] for i in range(n)]
kara=[]
to=[0]*n
for i in range(m):
  x,y=map(int,input().split())
  edge[x-1].append(y-1)
  to[y-1]+=1
for j in range(n):
  if to[j]==0:
    kara.append(j)
dp=[0]*n
while len(kara):
  go=kara.pop()
  for e in edge[go]:
    to[e]-=1
    if to[e]==0:
      kara.append(e)
    dp[e]=max(dp[e],dp[go]+1)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n, m = map(int, input().split())
outs = defaultdict(list)
rv = defaultdict(list)
ins = defaultdict(int)
for i in range(m):
    x, y = map(int, input().split())
    outs[x].append(y)
    rv[y].append(x)
    ins[y] += 1
q = deque(i for i in range(1, n + 1) if ins[i] == 0)
ans = []
while q:
    st = q.popleft()
    ans.append(st)
    for to in outs[st]:
        ins[to] -= 1
        if ins[to] == 0:
            q.append(to)

dp = [0] * (n + 1)
for value in ans:
    dp[value] += max([0]+[dp[i]+1 for i in rv[value]])
print(max(dp))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

sys.setrecursionlimit(10 ** 6)

n, m = na()
xy = nan(m)

g = [[] for _ in range(n)]
deg = [0] * n
for i in range(m):
    x, y = xy[i]
    x -= 1
    y -= 1
    g[x].append(y)
    deg[y] += 1

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

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in g[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return dp[v]

def bfs():
    q = deque()
    for i in range(n):
        if deg[i] == 0:
            q.append(i)
    dp = [0] * n
    while len(q):
        p = q.popleft()
        for v in g[p]:
            deg[v] -= 1
            if deg[v] == 0:
                q.append(v)
                dp[v] = max(dp[v], dp[p] + 1)
    return dp

ans = 0
dp = bfs()
for v in range(n):
    ans = max(ans, dp[v])

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

sys.setrecursionlimit(10 ** 6)

n, m = na()
xy = nan(m)

g = [[] for _ in range(n)]
for i in range(m):
    x, y = xy[i]
    x -= 1
    y -= 1
    g[x].append(y)

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

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in g[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return dp[v]

ans = 0
for v in range(n):
    ans = max(ans, dfs(v))

print(ans)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
sys.setrecursionlimit(10**5)
E = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)

dp = [-1]*N


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

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


for i in range(N):
    dp[i] = rec(i)
print(max(dp))

Submission status: Accepted

Solution code:
# longest path

import sys
from collections import defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    edge = defaultdict(lambda: [])

    memo = [0] * 110000
    done = [False] * 110000

    def dp(v):
        if done[v]:
            return memo[v]
        ans = 0
        for to in edge[v]:
            ans = max(ans, dp(to) + 1)
        done[v] = True
        memo[v] = ans
        return ans

    for i in range(M):
        u, v = map(int, input().split())
        edge[u].append(v)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
  x,y = map(int,input().split())
  graph[x].append(y)
memo = [0]*(n+1)
done = [False]*(n+1)
for i in range(1,n+1):
  if len(graph[i]) == 0:
    done[i] = True
def cnt(i):
  if done[i]:
    return memo[i]
  else:
    l = []
    for j in graph[i]:
      l.append(cnt(j))
    memo[i] = max(l)+1
    done[i] = True
    return memo[i]
ans = [0]*n
for i in range(n):
  ans[i] = cnt(i+1)
print(max(ans))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(x):
  if z[x]==-1:
  	z[x]=max([f(i) for i in v[x]]+[-1])+1
  return z[x]
n,m=map(int,raw_input().split())
v=[[] for _ in xrange(n)]
for x,y in [map(int,raw_input().split()) for _ in xrange(m)]:
  v[x-1].append(y-1)
z=[-1]*n
for i in xrange(n):
  if z[i]==-1:
    f(i)
print max(z)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

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

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def dfs(node,paths,dp,vis):
    vis[node]=True
    for i in range(0, len(paths[node])):
        if not vis[paths[node][i]]:
            dfs(paths[node][i],paths,dp,vis)
        dp[node]=max(dp[node],1+dp[paths[node][i]])
n,m=map(int,input().split())
paths=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    paths[a].append(b)
dp,vis=[0]*(n+1),[False]*(n+1)
for i in range(1,n+1):
    if not vis[i]:
        dfs(i,paths,dp,vis)
print(max(dp))

Submission status: Accepted

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

dp = [-1]*n

def DFS(node):
    ma = -1
    for c_node in graph[node]:
        if dp[c_node]>=0:
            tmp = dp[c_node]
        else:
            tmp = DFS(c_node)
        if tmp > ma:
            ma = tmp
    dp[node] = ma+1
    return ma+1

sys.setrecursionlimit(10**9)

for i in range(n):
    if dp[i]>=0:
        continue
    DFS(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
dst = [[] for _ in range(N)]
src = [[] for _ in range(N)]
for i in range(M):
    x, y = [int(z) - 1 for z in readline().split()]
    dst[x].append(y)
    src[y].append(x)


def solve():
    nodes = []
    nindex = [-1] * N

    def topsort(i):
        res = []
        if nindex[i] != -1:
            return
        for j in src[i]:
            topsort(j)
        nindex[i] = len(nodes)
        nodes.append(i)

    for i in range(N):
        topsort(i)
    dp = [0] * N
    dpi = [None] * N
    for i in range(N):
        node = nodes[i]
        plen = 0
        mj = None
        for j in src[node]:
            k = nindex[j]
            # print(">>", node, "- > ", j, ":", k)
            if plen < dp[k] + 1:
                plen = dp[k] + 1
                mj = j
        # print(">", node, "- > ", mj)
        dp[i] = plen
        dpi[i] = mj
    return max(dp)


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