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 g_longest_path(N, M, Edges):
    """
    N頂点M辺の有向グラフGが与えられる。Gは有向閉路を含まない。
    Gの有向パスのうち、最長のものについてその長さを求めよ。
    有向パスの長さとは、有向パスに含まれる辺の本数のことをいう。
    """
    import sys
    sys.setrecursionlimit(10**6)

    # 隣接リストでグラフを持つ(0-based)
    graph = [[] for _ in range(N)]
    for x, y in Edges:
        graph[x - 1].append(y - 1)

    # メモ化再帰
    # ある頂点vから辿っていけるパスの長さは、vに着くまでにどのようにパスを
    # 辿ってきたかと無関係(有向閉路がないため)なので、この方法が使える
    def memorized_recursive(v):
        if dp[v] != -1:
            return dp[v]  # 頂点vはすでに更新済み

        ret = 0
        # 頂点vから1つ辺を通って行ける頂点の集合に対して同じ計算を行う
        for nv in graph[v]:
            ret = max(ret, memorized_recursive(nv) + 1)
        dp[v] = ret  # メモに追加
        return ret

    ans = 0
    dp = [-1] * N  # dp[v]: ノードvを始点としたときの、Gの有効パスの長さの最大値
    # 各頂点に対して調べる
    for v in range(N):
        ans = max(ans, memorized_recursive(v))
    return ans

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(g_longest_path(N, M, Edges))

Submission status: Accepted

Solution code:
import collections
n, m = [int(i) for i in input().split()]
todc = collections.defaultdict(lambda: [])
lendc = collections.defaultdict(lambda: -1)


for k in range(m):
    i, j = [int(n) for n in input().split()]
    todc[j] += [i]


def maxlen(n):
    if len(todc[n]) == 0:
        lendc[n] = 0
        return 0
    else:
        m = 0
        for i in todc[n]:
            if lendc[i] == -1:
                lendc[i] = maxlen(i)
            m = max(m, lendc[i]+1)
        return m
       

def maxlen_stack(org_n):
    stack = [org_n]
    while stack:
        n = stack.pop()
        if lendc[n] != -1:
            continue        
        if len(todc[n]) == 0:
            lendc[n] = 0
        else:
            m = 0
            recursive = []
            for i in todc[n]:
                if lendc[i] == -1:
                    recursive.append(i)
                else:
                    m = max(m, lendc[i]+1)
            if recursive:
                stack += [n] + recursive
            else:
                lendc[n] = m         
    return lendc[org_n]

k = 0
for i in range(1, n+1):
    if lendc[i] == -1:
        #lendc[i] = maxlen(i)
        lendc[i] = maxlen_stack(i)
    k = max(k, lendc[i])
print(k)

Submission status: Accepted

Solution code:
import collections
n, m = [int(i) for i in input().split()]
todc = collections.defaultdict(lambda: [])
lendc = collections.defaultdict(lambda: -1)


for k in range(m):
    i, j = [int(n) for n in input().split()]
    todc[j] += [i]


def maxlen(n):
    if len(todc[n]) == 0:
        lendc[n] = 0
        return 0
    else:
        m = 0
        for i in todc[n]:
            if lendc[i] == -1:
                lendc[i] = maxlen(i)
            m = max(m, lendc[i]+1)
        return m
       

def maxlen_stack(org_n):
    stack = [org_n]
    while stack:
        n = stack.pop()
        if len(todc[n]) == 0:
            lendc[n] = 0
        else:
            m = 0
            recursive = []
            for i in todc[n]:
                if lendc[i] == -1:
                    recursive.append(i)
                else:
                    m = max(m, lendc[i]+1)
            if recursive:
                stack += [n] + recursive
            else:
                lendc[n] = m         
    return lendc[org_n]

k = 0
for i in range(1, n+1):
    if lendc[i] == -1:
        #lendc[i] = maxlen(i)
        lendc[i] = maxlen_stack(i)
    k = max(k, lendc[i])
print(k)

Submission status: Accepted

Solution code:
import collections, sys

n, m = map(int, input().split())
pres = collections.defaultdict(list)
nxts = collections.defaultdict(list)
for line in sys.stdin:
    x, y = map(int, line.split())
    pres[y].append(x)
    nxts[x].append(y)

stack, count, nodes = [], [0], []
for node in range(1, n + 1):
    count.append(len(pres[node]))
    if count[node] == 0:
        stack.append(node)

while stack:
    node = stack.pop()
    nodes.append(node)
    for nxt in nxts[node]:
        count[nxt] -= 1
        if count[nxt] == 0:
            stack.append(nxt)

dp = [0] * (n + 1)
for node in nodes:
    for pre in pres[node]:
        dp[node] = max(dp[node], dp[pre] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
raw_input = sys.stdin.readline
N,M = map(int,raw_input().split())
paths = [[] for x in range(N)]
inc = [0 for x in range(N)]
for i in range(M):
    a,b = map(int,raw_input().split())
    paths[a-1].append(b-1)
    inc[b-1] += 1
q = []
for i in range(N):
    if not inc[i]:
        q.append(i)
dp = [0 for x in range(N)]
while q:
    c = q.pop(0)
    for i in paths[c]:
        dp[i] = max(dp[i],dp[c]+1)
        inc[i] -= 1
        if not inc[i]:
            q.append(i)
print max(dp)

Submission status: Accepted

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

n,m=map(int,input().split())
d={}
dp={}
n=[]

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

def lp(a):
	if a in dp:
		return dp[a]
	if a not in d:
		dp[a]=1
		return 1
	ans=0
	for i in d[a]:
		ans=max(ans,1+lp(i))
	dp[a]=ans
	return ans

p=0
for i in n:
	p=max(p,lp(i))
print(p-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

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

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

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


def dfs(u):
    if dp[u] != 0 or len(graph[u]) == 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


for i in range(N):
    dfs(i)
print(max(dp))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

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

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

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


def dfs(u):
    if dp[u] != 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


for i in range(N):
    dfs(i)
print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from sys import stdin
N, M = map(int, stdin.readline().split())
x = []
y = []
count_in = defaultdict(int)
graph = [[] for _ in range(N)]
graph = defaultdict(list)
graph_reverse = defaultdict(list)
for _ in range(M):
    tmpx, tmpy = map(int, stdin.readline().split())
    x.append(tmpx-1)
    y.append(tmpy-1)
    graph[tmpx-1].append(tmpy-1)
    graph_reverse[tmpy-1].append(tmpx-1)
    count_in[tmpy-1] += 1
q = deque(v for v in range(N) if count_in[v] == 0)
res = []
while q:
    v = q.popleft()
    res.append(v)
    for v_out in graph[v]:
        count_in[v_out] -= 1
        if count_in[v_out] == 0:
            q.append(v_out)

dp = [0 for _ in range(N)]
dp[0] = 0
point2order = defaultdict(int)
for i in range(N):
    point2order[res[i]] = i
    for v in graph_reverse[res[i]]:
        dp[i] = max(dp[i], dp[point2order[v]]+1)
print(dp[N-1])

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

memo = [0]*N

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

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

print(max(memo))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(v):
    if cache[v] > -1:
        return cache[v]
    lv = links[v]
    cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
    return ret


n, m = map(int, input().split())
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    links[x - 1].add(y - 1)

print(max(map(dfs, range(n))))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(v):
    if cache[v] > -1:
        return cache[v]
    lv = links[v]
    cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
    return ret


n, m = map(int, input().split())
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].add(y)

print(max(map(dfs, range(n))))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(v):
    if cache[v] > -1:
        return cache[v]
    lv = links[v]
    cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
    return ret


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))

Submission status: Accepted

Solution code:
# トポロジカルソート->簡単なDP
import sys
sys.setrecursionlimit(300000) # ないとerr

N,M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int, input().split())
    adj[x-1].append(y-1) 
# print("adj list: ", adj)

visited = [False] * N
topo_order = [] # sort後を格納

# topological sort by DFS
def dfs_visit(node):
    global visited, topo_order
    if visited[node]: return
    visited[node] = True
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    # 帰りがけに追加
    topo_order.append(node)
    # print(topo_order)

# topological sort main
for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]
# print("topo_order: ", topo_order)

dp = [0]*N

for node in topo_order:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node]+1)
print(max(dp))
# print(dp)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
h = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  h[y].append(x)
topo = []
hukasa = [0] * n
hairu = [0]*n
que = deque([])
for i in range(n):
  hairu[i] = len(h[i])
  if hairu[i] == 0:
    topo.append(i)
    que.append(i)
def dfs(x):
  for i in g[x]:
    hairu[i]-=1
    if hairu[i] == 0:
      topo.append(i)
      que.append(i)
while que:
  x = que.popleft()
  dfs(x)
def dfs2(x):
  for i in g[x]:
    hukasa[i] = max(hukasa[i],hukasa[x]+1)
for i in topo:
  dfs2(i)
print(max(hukasa))

Submission status: Accepted

Solution code:
from collections import defaultdict
debug = print
def debug(*va): pass

def longest_by_topological_sort(N, nexts, prevs):
    visited = [-1] * N
    max_dist = 0
    que = list(range(N))
    while len(que):
        p = que.pop()
        if visited[p] == -1:
            if all(visited[q] != -1 for q in prevs[p]):
                dist = 0
                for q in prevs[p]:
                    dist = max(dist, visited[q] + 1)
                visited[p] = dist
                max_dist = max(max_dist, dist)
                for n in nexts[p]:
                    que.append(n)
    return max_dist

def test_separate():
    import time
    N = 10**5
    t0 = time.time()
    print(longest_by_topological_sort(N, defaultdict(list), defaultdict(list)))
    print('elapsed', time.time() - t0)

def test_fanout():
    import time
    N = 10**5
    nn, pp = defaultdict(list), defaultdict(list)
    for i in range(1, N):
        nn[0].append(i)
        pp[i].append(0)
    t0 = time.time()
    print(longest_by_topological_sort(N, nn, pp))
    print('elapsed', time.time() - t0)

def test_middle():
    import time
    N = 10**5
    nn, pp = defaultdict(list), defaultdict(list)
    for i in range(1, N):
        # fanout
        nn[0].append(i)
        pp[i].append(0)
        # fanin
        nn[i].append(1)
        pp[1].append(i)
    t0 = time.time()
    print(longest_by_topological_sort(N, nn, pp))
    print('elapsed', time.time() - t0)

if __name__ == '__main__':
    N, M = map(int, input().split())

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

    max_dist = longest_by_topological_sort(N, nextnodes[0], nextnodes[1])
    print(max_dist)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
memo=[-1]*N
def rec(x):
  if memo[x]>=0:
    return memo[x]
  res=0
  if not G[x]:
    memo[x]=0
    return 0
  for y in G[x]:
    res=max(rec(y),res)
  memo[x]=res+1
  return memo[x]
for i in range(N):
  rec(i)
print(max(memo))

Submission status: Accepted

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

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

#REVEDGE=[[] for i in range(N+1)]
EDGELIST=[[] for i in range(N+1)]
LEAF=[]
for x,y in EDGE:
    #REVEDGE[y].append(x)
    EDGELIST[x].append(y)

for i in range(1,N+1):
    if EDGELIST[i]==[]:
        LEAF.append(i)

DIST=[-1]*(N+1)
for l in LEAF:
    DIST[l]=0

def distance(x):
    if DIST[x]!=-1:
        return DIST[x]
    ANS=0
    for to in EDGELIST[x]:
        if ANS<distance(to)+1:
            ANS=distance(to)+1

    DIST[x]=ANS
    return ANS

for i in range(1,N+1):
    DIST[i]=distance(i)

print(max(DIST))

Submission status: Accepted

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

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

#REVEDGE=[[] for i in range(N+1)]
EDGELIST=[[] for i in range(N+1)]
LEAF=[]
for x,y in EDGE:
    #REVEDGE[y].append(x)
    EDGELIST[x].append(y)

for i in range(1,N+1):
    if EDGELIST[i]==[]:
        LEAF.append(i)

DIST=[-1]*(N+1)
for l in LEAF:
    DIST[l]=0

def distance(x):
    if DIST[x]!=-1:
        return DIST[x]
    ANS=0
    for to in EDGELIST[x]:
        if ANS<distance(to)+1:
            ANS=distance(to)+1

    DIST[x]=ANS
    return ANS

for i in range(1,N+1):
    DIST[i]=distance(i)

print(max(DIST))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
is_root = [True for _ in range(n)]

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

dp = [0 for _ in range(n)]
def dfs(x):
	global dp
	for c in edges[x]:
		rank[c] -= 1
		dp[c] = max(dp[c], dp[x]+1)
		if rank[c] == 0:
			dfs(c)
	return

for i in range(n):
	if is_root[i]:
		dfs(i)

#print(dp)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
is_root = [True for _ in range(n)]

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

dp = [0 for _ in range(n)]
def dfs(x):
	global dp
	for c in edges[x]:
		rank[c] -= 1
		dp[c] = max(dp[c], dp[x]+1)
		if rank[c] == 0:
			dfs(c)
	return

for i in range(n):
	if is_root[i]:
		dfs(i)

#print(dp)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[-1]*N
def f(x):
    if dp[x]!=-1:
        return dp[x]
    if len(table[x])==0:
        return 0
    t=0
    for i in table[x]:
        t=max(t,f(i)+1)
    dp[x]=t
    return t
for i in H:
    f(i)
print(max(dp))

Submission status: Accepted

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


dist = [0] * n
checked = [False] * n
def check(x):
  if checked[x]:return dist[x]
  ret = 0
  for fr in rev_edges[x]:
    ret = max(ret, check(fr) + 1)
  dist[x] = ret
  checked[x] = True
  return ret

for i in range(n):
  check(i)
print(max(dist))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
fin = sys.stdin.readline


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    x, y = [int(elem) - 1 for elem in fin().split()]
    adj[x].append(y)

visited = [False] * N
topo_order = []
# topological sort by DFS
def dfs_visit(node):
    visited[node] = True
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    topo_order.append(node)


for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]

dp = [0] * N
for node in topo_order[:-1]:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node] + 1)

print(max(dp))

Submission status: Accepted

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

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


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


T = topological_sort(G)
dist = [0] * N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v], dist[n] + 1)

print(max(dist))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
es = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

indeg = [0 for i in range(N)]
outdeg = [[] for i in range(N)]
for a,b in es:
    indeg[b] += 1
    outdeg[a].append(b)

heads = []
for i in range(N):
    if indeg[i]: continue
    heads.append(i)

dp = [0] * N
while heads:
    a = heads.pop()
    for b in outdeg[a]:
        indeg[b] -= 1
        if indeg[b] == 0:
            heads.append(b)
        dp[b] = max(dp[b], dp[a] + 1)
print(max(dp))

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:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
xy = []

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

dp = [0]*n
for _ in range(m):
    x,y = li_()
    ins[y] += 1
    graph[x].append(y)
    
stack = []
for i in range(n):
    if ins[i] == 0:
        stack.append(i)

while stack:
    nex_stack = []
    for point in stack:
        for nexp in graph[point]:
            dp[nexp] = max(dp[nexp], dp[point]+1)
            ins[nexp] -= 1
            if ins[nexp] == 0:
                nex_stack.append(nexp)
                
    stack = nex_stack
    
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    G[x-1].add(y-1)
dp=[-1 for i in range(N)]
def search(k):
    if dp[k]!=-1:
        return dp[k]
    res=0
    for r in G[k]:
        if search(r)+1>res:
            res=search(r)+1
    dp[k]=res
    return res
for i in range(N):
    if dp[i]==-1:
        search(i)
print(max(dp))

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
graph = [[] for _ in xrange(n)]
ind = [0 for _ in xrange(n)]
outd = [0 for _ in xrange(n)]
used = [False for _ in xrange(n)]
topo = []
cnt = 0

for i in xrange(m):
    u, v = map(int, raw_input().split())
    ind[v-1] += 1
    outd[u-1] += 1
    graph[u-1].append(v-1)
    
for i in xrange(n):
    if ind[i] == 0 and used[i] == False:
        topo.append(i)
        used[i] = True

while cnt < n:
    u = topo[cnt]
    for v in graph[u]:
        ind[v] -= 1
        if ind[v] == 0 and used[v] == False:
            used[v] = True
            topo.append(v)
    cnt += 1
    
dp = [0 for _ in xrange(n)]
for u in topo:
    for v in graph[u]:
        dp[v] = max(dp[v], dp[u] + 1)
res = max(dp)
print res

Submission status: Accepted

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

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

memo = [-1]*N
def dfs(v):
    if memo[v] != -1:
        return memo[v]
    memo[v] = r = max(dfs(w) for w in G[v]) + 1 if G[v] else 0
    return r
print(max(dfs(v) for v in range(N)))

Submission status: Runtime Error

Solution code:
def dfs(now):
  if v[now]:return v[now]
  res=1
  for to in e[now]:
    res=max(res,dfs(to)+1)
  v[now]=res
  return res
n,m=map(int,input().split())
e=[[]for _ in range(n+1)]
for i in range(m):
  x,y=map(int,input().split())
  e[x]+=[y]
v=[0]*(n+1)
v[0]=1
ans=0
for i in range(n+1):
  ans=max(ans,dfs(i))
print(ans-1)

Submission status: Runtime Error

Solution code:
def memo(v):
    if dp[v]!=-1:return dp[v]
    ans = 0
    for next_v in g[v]:
        ans = max(ans,memo(next_v)+1)
    dp[v] = ans
    return dp[v]

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

ans = 0
for v in range(1,n+1):
    ans = max(ans, memo(v))
    
print(ans)

Submission status: Runtime Error

Solution code:
def memo(v):
    if dp[v]!=-1:return dp[v]
    ans = 0
    for next_v in g[v]:
        ans = max(ans,memo(next_v)+1)
    dp[v] = ans
    return dp[v]

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

ans = 0
for v in range(1,n+1):
    print("v={}".format(v))
    ans = max(ans, memo(v))
    
print(ans)

Submission status: Runtime Error

Solution code:
def memo(v):
    if dp[v]!=-1:return dp[v]
    ans = 0
    for next_v in g[v]:
        ans = max(ans,memo(next_v)+1)
    dp[v] = ans
    return dp[v]

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

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

Submission status: Runtime Error

Solution code:
def main():
    n,m = map(int,input().split())
    g = [[] for _ in range(n+1)]
    for _ in range(m):
        x,y = map(int,input().split())
        g[x].append(y)

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

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

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

    print(ans)

main()

Submission status: Runtime Error

Solution code:
def main():
    n,m = map(int,input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        x,y = map(int,input().split())
        g[x].append(y)

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

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

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

    print(ans)

main()

Submission status: Runtime Error

Solution code:
def f(x):
    if flg[x]:
        flg[x] = 0
        p = 0
        for y in glaph[x]:
            p = max(p,f(y)+1)
        dp[x] = p
    return dp[x]
n,m = map(int,input().split())
flg = [1]*(n+1)
dp = [0]*(n+1)
glaph = [[] for i in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    glaph[x].append(y)
ans = 0
for i in range(1,n+1):
    ans = max(ans,f(i))
print(ans)

Submission status: Runtime Error

Solution code:
temparr = input()
from heapq import heappush, heappop
temparr = temparr.split()
n = int(temparr[0])
edg = int(temparr[1])
dicts = {}
secdict = {}
firstdict = {}
for e in range(edg):
    temparr = input()
    temparr = temparr.split()
    edgearr = []
    for i in temparr:
        edgearr.append(int(i))
    first = int(edgearr[0])
    sec = int(edgearr[1])
    if first not in dicts:
        dicts[first] = []
    dicts[first].append(sec)
    if sec not in secdict:
        secdict[sec] = 1 
    if first not in firstdict:
        firstdict[first] = 1 
        

tail = []
ans = {}
for i in range(1, n + 1):
    if i not in firstdict:
        tail.append(i)
        ans[i] = 0

def dfs(node):
    global ans, dicts
    # if node in ans:
    #     return ans[node]
    if node not in  dicts:
        return 0  
    best = 0 
    for neigh in dicts[node]:
        curnew = dfs(neigh) + 1
        if curnew > best:
            best = curnew
    ans[node] = best 
    return best
ans2 = 0 
for i in range(1, n + 1):
    ans2 = max(dfs(i), ans2)
print(ans2)

Submission status: Runtime Error

Solution code:
temparr = input()
from heapq import heappush, heappop
temparr = temparr.split()
n = int(temparr[0])
edg = int(temparr[1])
dicts = {}
secdict = {}
firstdict = {}
for e in range(edg):
    temparr = input()
    temparr = temparr.split()
    edgearr = []
    for i in temparr:
        edgearr.append(int(i))
    first = int(edgearr[0])
    sec = int(edgearr[1])
    if first not in dicts:
        dicts[first] = []
    dicts[first].append(sec)
    if sec not in secdict:
        secdict[sec] = 1 
    if first not in firstdict:
        firstdict[first] = 1 
        

tail = []
ans = {}
for i in range(1, n + 1):
    if i not in firstdict:
        tail.append(i)
        ans[i] = 0

def dfs(node):
    global ans, dicts
    if node in ans:
        return ans[node]
    if node not in  dicts:
        return 0  
    best = 0 
    for neigh in dicts[node]:
        curnew = dfs(neigh) + 1
        if curnew > best:
            best = curnew
    ans[node] = best 
    return best
ans2 = 0 
for i in range(1, n + 1):
    ans2 = max(dfs(i), ans2)
print(ans2)

Submission status: Runtime Error

Solution code:
temparr = input()
from heapq import heappush, heappop
temparr = temparr.split()
n = int(temparr[0])
edg = int(temparr[1])
dicts = {}
secdict = {}
firstdict = {}
for e in range(edg):
    temparr = input()
    temparr = temparr.split()
    edgearr = []
    for i in temparr:
        edgearr.append(int(i))
    first = int(edgearr[0])
    sec = int(edgearr[1])
    if first not in dicts:
        dicts[first] = []
    dicts[first].append(sec)
    if sec not in secdict:
        secdict[sec] = 1 
    if first not in firstdict:
        firstdict[first] = 1 
        
head = []
for i in range(1, n + 1):
    if i not in secdict:
        heappush(head, (0, i))
tail = []
ans = {}
for i in range(1, n + 1):
    if i not in firstdict:
        tail.append(i)
        ans[i] = 0
maxdist = [0 for _ in range(n + 1)]

#print(ans)



def dfs(node):
    global ans, dicts
    #print(node)
    if node in ans:
        return ans[node]
    if node not in  dicts:
        return 0  
    best = 0 
    for neigh in dicts[node]:
        curnew = dfs(neigh) + 1
        if curnew > best:
            best = curnew
    
    ans[node] = best 
    return best

getmax =  0 
ans2 = 0 
for i in range(1, n + 1):
    ans2 = max(dfs(i), ans2)
print(ans2)

# while head:
#     cur = heappop(head)
#     curdis = int(cur[0])
#     node = cur[1]
#     nextdis = maxdist[node] + 1
#     if node not in dicts:
#         continue 
#     for neigh in dicts[node]:
#         if maxdist[neigh] < nextdis:
#             negdis = nextdis * -1
#             maxdist[neigh] = nextdis
#             heappush(head,(nextdis, neigh))

# print(max(maxdist))

Submission status: Runtime Error

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
\# input処理を高速化する
input = sys.stdin.readline

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

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

dp = [-1] * N

# rec(v) 頂点vを始点としたとき有効パスの長さの最大値
def rec(v):
    #print(dp, v)
    if dp[v] != -1:
        return dp[v] # 既に更新済み

    ans = 0
    lst_nv = lst_edge[v]
    for nv in lst_nv:
        ans = max(ans, rec(nv) + 1)
    dp[v] = ans # メモしながらリターン
    return dp[v]

ans_memo = 0
for i in range(N):
    ans_memo = max(ans_memo, rec(i))

print(ans_memo)

Submission status: Runtime Error

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

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

dp = [-1] * N

# rec(v) 頂点vを始点としたとき有効パスの長さの最大値
def rec(v):
    #print(dp, v)
    if dp[v] != -1:
        return dp[v] # 既に更新済み

    ans = 0
    lst_nv = lst_edge[v]
    for nv in lst_nv:
        ans = max(ans, rec(nv) + 1)
    dp[v] = ans # メモしながらリターン
    return dp[v]

ans_memo = 0
for i in range(N):
    ans_memo = max(ans_memo, rec(i))

print(ans_memo)

Submission status: Runtime Error

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

#import
#import math
#import numpy as np
N, M = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(M)]

G = {i: [] for i in range(1, N + 1)}

for x, y in xy:
    G[x].append(y)

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

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

    t = 0

    for g in G[num]:
        t = max(t, dfs(g) + 1)

    dp[num] = t
    return t

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

print(ans)