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: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(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: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(100000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(dfs(u) for u in lv) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(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(dfs(v) for v in sss))

Submission status: Time Limit Exceeded

Solution code:
f=lambda:map(int,input().split())
N,M=f()
N+=1;V=[-1]*N
Q=list(range(N))
F,B=eval('{i:[]for i in Q},'*2)
for i in'0'*M:x,y=f();F[x]+=[y];B[y]+=[x]
while Q:
 p=Q.pop();S=[1+V[q]for q in B[p]]
 if all(S)and V[p]<0:V[p]=max(S+[0]);Q+=F[p]
print(max(V))

Submission status: Time Limit Exceeded

Solution code:
f=lambda:map(int,input().split())
N,M=f()
N+=1;V=[-1]*N
Q=list(range(N))
F,B=eval('{i:[]for i in Q},'*2)
exec('x,y=f();F[x]+=[y];B[y]+=[x];'*M)
while Q:
 p=Q.pop();S=[1+V[q]for q in B[p]]
 if all(S)and V[p]<0:V[p]=max(S+[0]);Q+=F[p]
print(max(V))

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
dummynode = N
N += 1

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)

# connect all nodes:
# dummynode -> all nodes
for i in range(N - 1):
    nextnodes[0][dummynode].append(i)
    nextnodes[1][i].append(dummynode)

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

max_dist = longest_by_topological_sort(dummynode, nextnodes[0], nextnodes[1])
max_dist -= 1 # dummy

print(max_dist)

Submission status: Time Limit Exceeded

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

    return ANS

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

print(max(DIST))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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)

from collections import deque
QUE = deque(LEAF)

DIST=[0]*(N+1)

while QUE:
    x=QUE.pop()

    for to in REVEDGE[x]:
        if DIST[to]<DIST[x]+1:
            DIST[to]=DIST[x]+1
            QUE.appendleft(to)

print(max(DIST))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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)

from collections import deque
QUE = deque(LEAF)

DIST=[0]*(N+1)

while QUE:
    x=QUE.pop()

    for to in REVEDGE[x]:
        if DIST[to]<DIST[x]+1:
            DIST[to]=DIST[x]+1
            QUE.append(to)

print(max(DIST))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

LEAF=[]
for x,y in EDGE:
    REVEDGE[y].append(x)
    LEAF.append(x)

LEAF=list(set(range(1,N+1)) - set(LEAF))

from collections import deque
QUE = deque(LEAF)

DIST=[0]*(N+1)

while QUE:
    x=QUE.pop()

    for to in REVEDGE[x]:
        if DIST[to]<DIST[x]+1:
            DIST[to]=DIST[x]+1
            QUE.append(to)

print(max(DIST))

Submission status: Time Limit Exceeded

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=[0]*N
def f(x):
    if len(table[x])==0:
        return
    for i in table[x]:
        if dp[i]<dp[x]+1:
            dp[i]=dp[x]+1
            f(i)
    return
for i in H:
    f(i)
print(max(dp))

Submission status: Time Limit Exceeded

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=[0]*N
def f(x):
    if len(table[x])==0:
        return
    for i in table[x]:
        dp[i]=max(dp[x]+1,dp[i])
        f(i)
    return
for i in H:
    f(i)
print(max(dp))

Submission status: Time Limit Exceeded

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

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

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

sys.setrecursionlimit(10 ** 9)


def dfs(num_v):
    if len(graph[num_v]) == 0:
        return
    for to in graph[num_v].keys():
        dp[to] = max(dp[to], dp[num_v] + 1)
        dfs(to)


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

Submission status: Time Limit Exceeded

Solution code:
import heapq
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)
hukasa = [0]*n
MIN = float("inf")
for i in range(n):
  MIN = min(MIN,len(h[i]))
def dfs(x,y):
  for k in g[x]:
    if hukasa[k] < y+1:
      heapq.heappush(que,[-(y+1),k])
for i in range(n):
  if MIN == len(h[i]):
    que = [[0,i]]
    heapq.heapify(que)
    while que:
      y,x = heapq.heappop(que)
      if hukasa[x] < -y:
        hukasa[x] = -y
      dfs(x,-y)
print(max(hukasa))

Submission status: Time Limit Exceeded

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)
hukasa = [0]*n
MIN = float("inf")
for i in range(n):
  MIN = min(MIN,len(h[i]))
def dfs(x,y):
  for k in g[x]:
    if hukasa[k] < y+1:
      que.append([k,y+1])
for i in range(n):
  if MIN == len(h[i]):
    que = deque([])
    que.append([i,0])
    while que:
      x,y = que.popleft()
      hukasa[x] = y
      dfs(x,y)
for i in range(n):
  hukasa[i] = [hukasa[i],i]
hukasa.sort()
dp = [0] * n
for l,i in hukasa:
  for j in g[i]:
    if dp[j] < dp[i]+1:
      dp[j] = dp[i]+1
print(max(dp))

Submission status: Time Limit Exceeded

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)
hukasa = [float("inf")]*n
MIN = float("inf")
for i in range(n):
  MIN = min(MIN,len(h[i]))
def dfs(x,y):
  for k in g[x]:
    if hukasa[k] > y+1:
      hukasa[k] = y+1
      que.append([k,y+1])
for i in range(n):
  if MIN == len(h[i]):
    que = deque([])
    que.append([i,0])
    hukasa[i] = 0
    while que:
      x,y = que.popleft()
      dfs(x,y)
for i in range(n):
  hukasa[i] = [hukasa[i],i]
hukasa.sort()
dp = [0] * n
while True:
  flag = 1
  for l,i in hukasa:
    for j in g[i]:
      if dp[j] < dp[i]+1:
        dp[j] = dp[i]+1
        flag = 0
  if flag:
    break
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
dp = [0] * n
que = deque([])
for i in range(n):
  que.append(i)
han = set()
for i in range(n):
  han.add(i)
while que:
  i = que.popleft()
  han.remove(i)
  for j in g[i]:
    if dp[j] < dp[i]+1:
      dp[j] = dp[i]+1
      if j not in han:
        que.append(j)
        han.add(j)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
dp = [0] * n
while True:
  flag = 1
  for i in range(n):
    for j in g[i]:
      if dp[j] < dp[i]+1:
        dp[j] = dp[i]+1
        flag = 0
  if flag:
    break
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+10)
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 ans

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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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: Accepted

Solution code:
temparr = input()
from heapq import heappush, heappop

import sys
x=150000
sys.setrecursionlimit(x)
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 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: Accepted

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: Accepted

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

def main():
    n, m = map(int, input().split())

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

    dp = [-1] * n
    def dfs(node):
        if len(edges[node]) == 0:
            dp[node] = 0
        else:
            max_len = 0
            for new_node in edges[node]:
                if dp[new_node] == -1:
                    dfs(new_node)
                if max_len < dp[new_node]:
                    max_len = dp[new_node]
            dp[node] = max_len + 1

    for node in range(n):
        if dp[node] == -1:
            dfs(node)

    print(max(dp))

main()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10 ** 7)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfs(self, node):
        ans = 0
        for child in self.adj[node]:
            ans = max(ans, 1 + self.dfs(child))
        return ans

    def dfsWithMemo(self, node, memo, visited):
        if(visited[node]):
            return memo[node]
        visited[node] = True
        for child in self.adj[node]:
            memo[node] = max(
                memo[node], 1 + self.dfsWithMemo(child, memo, visited))
        return memo[node]

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    # o(n^2) solution
    def findLongestPathNaive(self):
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfs(i))
        return ans

    # o(n) solution
    def findLongestPathWithMemo(self):
        visited = [False] * self.n
        memo = [0] * self.n
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithMemo(i, memo, visited))
        return ans

    # O(n) solution
    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    # print(dag.findLongestPathNaive())
    #  print(dag.findLongestPathWithMemo())
    print(dag.findLongestPathWithDp())


main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfs(self, node):
        ans = 0
        for child in self.adj[node]:
            ans = max(ans, 1 + self.dfs(child))
        return ans

    def dfsWithMemo(self, node, memo, visited):
        if(visited[node]):
            return memo[node]
        visited[node] = True
        for child in self.adj[node]:
            memo[node] = max(
                memo[node], 1 + self.dfsWithMemo(child, memo, visited))
        return memo[node]

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    # o(n^2) solution
    def findLongestPathNaive(self):
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfs(i))
        return ans

    # o(n) solution
    def findLongestPathWithMemo(self):
        visited = [False] * self.n
        memo = [0] * self.n
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithMemo(i, memo, visited))
        return ans

    # O(n) solution
    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    # print(dag.findLongestPathNaive())
    print(dag.findLongestPathWithMemo())
    # print(dag.findLongestPathWithDp())


main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(list)
for _ in range(m):
  x,y=map(int,input().split())
  d[x-1].append(y-1)

dp=[-1]*n

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

res=0
for v in range(n):
  res=max(res,rec(v))
print(res)

Submission status: Accepted

Solution code:
def getval():
    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)
    return n,m,g

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    #Loop through each vertex
    for i in range(n):
        #If already computed: pass
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            cur = idx[0]
            #If not visited
            if not visited[cur]:
                visited[cur] = True
                #If there are vertices that can be reached
                if g[cur]:
                    prev.append(cur)
                    #Append to q
                    for j in g[cur]:
                        q.append([j,cur])
                    continue
                #No vertices to be reached
                else:
                    d[cur] = 0
                    temp[idx[1]].append(0)
            #If it has been visited in some way
            else:
                #If the distance hasn't been computed
                if d[cur] == -1:
                    d[cur] =  1 + max(temp[cur])
                if idx[1] != -1:
                    temp[idx[1]].append(d[cur])
            #If this is the first vertex
            if prev[-1] == -1:
                break
            #If the next vertex has the same parent vertex
            if q:
                if q[-1][1]==idx[1]:
                    continue
            #Otherwise, return to the parent node
            par = prev.pop(-1)
            q.append([par,prev[-1]])

    print(max(max(d),0))

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Submission status: Accepted

Solution code:
def getval():
    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)
    return n,m,g

def main(n,m,g):
    d = [-1 for i in range(n)]
    visited = [False for i in range(n)]
    temp = [[] for i in range(n)]
    ans = 0
    #print(g)
    #print(visited)
    for i in range(n):
        if d[i] != -1:
            continue
        q = [[i,-1]]
        prev = [-1]
        while q:
            idx = q.pop(-1)
            #print(i,idx,q,d)
            if not visited[idx[0]]:
                visited[idx[0]] = True
                if g[idx[0]]:
                    prev.append(idx[0])
                    for j in g[idx[0]]:
                        q.append([j,idx[0]])
                else:
                    d[idx[0]] = 0
                    temp[idx[1]].append(0)
                    if idx[1]==-1:
                        break
                    if prev[-1]!=-1 and q:
                        #print(q)
                        if q[-1][1]==idx[1]:
                            continue
                    bef = prev.pop(-1)
                    q.append([bef,prev[-1]])
            else:
                if d[idx[0]] == -1:
                    d[idx[0]] = 1 + max(temp[idx[0]])
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                else:
                    if idx[1]!=-1:
                        temp[idx[1]].append(d[idx[0]])
                if prev[-1]!=-1 and q:
                    #print(q)
                    if q[-1][1]==idx[1]:
                        continue
                if idx[1]==-1:
                    break
                bef = prev.pop(-1)
                q.append([bef,prev[-1]])   
    print(max(max(d),0))
    #print(d)
                

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Submission status: Accepted

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

n, m = map(int, input().split())
edges = [[]*n for _ in range(n)]
#DAGみたらDPを考える！

#メモ化再帰
visited = [False]*n
memo = [0]*n
def dp(v):
    if visited[v]:
        return memo[v]
    ret = 0
    for child in edges[v]:
        ret = max(ret, dp(child)+1)
    visited[v] = True
    memo[v] = ret
    return ret


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

ans = 0
for i in range(n):
    ans = max(ans, dp(i))
print(ans)
#print(memo)

Submission status: Accepted

Solution code:
def li():
    return [int(x) for x in input().split()]

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

INF = 10 ** 60

G = defaultdict(list)

N, M = li()

for _ in range(M):
    x, y = li()
    G[x].append(y)

dp = [-1] * (10 ** 5 + 1)

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for cv in G[v]:
        ret = max(ret, dfs(cv) + 1)
    dp[v] = ret
    return ret


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

print(ans)

Submission status: Accepted

Solution code:
def li():
    return [int(x) for x in input().split()]

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

INF = 10 ** 60

G = defaultdict(list)

N, M = li()

for _ in range(M):
    x, y = li()
    G[x].append(y)

dp = [-1] * (10 ** 5 + 100)

def dfs(v):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for cv in G[v]:
        ret = max(ret, dfs(cv) + 1)
    dp[v] = ret
    return ret


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

print(ans)

Submission status: Accepted

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


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

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

# dp[i] : iを始点とする最長経路
dp = [0] * N
seen = [0] * N

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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

dp = [-1]*N
def rec(v):
  if dp[v] != -1:
    return dp[v]
  
  res = 0
  for nv in graph[v]:
    res = max(res, rec(nv)+1)
  dp[v] = res
  return res

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

Submission status: Accepted

Solution code:
# import sys
import sys,os,io
# input = sys.stdin.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)

def dfs(start):
  stack = [start]
  while stack:
    v = stack[-1]
    marker = 0
    path_l[v] = 0
    for u in edge[v]:
      if path_l[u]==-1: #子へ降ろす
        marker = 1
        stack.append(u)
      else: #子から吸い上げる
        #吸い上げる際の個々の処理
        path_l[v] = max(path_l[v], path_l[u]+1)
    if marker==0:
      stack.pop()
  return

path_l = [-1]*N
for i in range(N):
  if path_l[i]==-1:
    dfs(i)
ans = max(path_l)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)

def dfs(start):
  stack = [start]
  while stack:
    v = stack[-1]
    marker = 0
    path_l[v] = 0
    for u in edge[v]:
      if path_l[u]==-1: #子へ降ろす
        marker = 1
        stack.append(u)
      else: #子から吸い上げる
        #吸い上げる際の個々の処理
        path_l[v] = max(path_l[v], path_l[u]+1)
    if marker==0:
      stack.pop()
  return

path_l = [-1]*N
for i in range(N):
  if path_l[i]==-1:
    dfs(i)
ans = max(path_l)
print(ans)

Submission status: Accepted

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

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

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

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

def f(x):
    if dp[x] != -1:
        return dp[x]

    t = 0
    for v in V[x]:
        t = max(t, f(v)+1)

    dp[x] = t
    return dp[x]

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

print(t)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n,m = map(int,input().split())
d = defaultdict(list)
deg = [0]*n  # 各頂点の入次数

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

que = deque([])
for v in range(n):
    if deg[v] == 0:
        que.append(v)

dp = [0]*100100

while que:
    v = que.popleft()
    for nv in d[v]:
        deg[nv] -= 1  # エッジ(v,nv)を破壊
        if deg[nv] == 0:
            que.append(nv)  # 入次数が0になったらキューに追加
            dp[nv] = max(dp[nv],dp[v]+1)  # ソースからnvまでの最長距離を確定

res = 0
for v in range(n):
    res = max(res,dp[v])
print(res)

Submission status: Accepted

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

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

dp = [-1]*n

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

res = 0
for v in range(n):
    res = max(res,rec(v))
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)

flag = [False] * (N + 1)
dp = [0] * (N + 1)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return dp[x]

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