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: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

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

graph = [[] for i in range(n + 1)]

for i in range(1, n + 1):
    graph[0].append(i)

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

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


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

    if len(graph[root]) == 0:
        dp[root] = 0
        return 0

    for i in graph[root]:
        dp[root] = max(dp[root], 1 + dfs(i))

    return dp[root]
    '''
    return 5

print(dfs(0)-1)

Submission status: Wrong Answer

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

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

Q = deque([])
for i in range(N):
    if Y[i] == 0:
        Q.append(i)
        
while len(Q) > 0:
    i = Q.popleft() # iは終着点
    for x in X[i]: # xはiとつながっている頂点
        dp[x] = dp[i]+1
        Y[x] -= 1
        if Y[x] == 0:
            Q.append(x)
print(dp)

Submission status: Wrong Answer

Solution code:
import sys

N,M=map(int,sys.stdin.readline().rstrip().split())
road_from=[[] for i in range(N+1)]
road_to=[[] for i in range(N+1)]
for i in range(M):
    x,y=map(int,sys.stdin.readline().rstrip().split())
    road_from[x].append(y)
    road_to[y].append(x)

# dp[i] = 頂点iまでの最長経路
dp = [0 for i in range(N+1)]
updated=True
for i in range(1,N+1):
    for j in road_to[i]:
        dp[i] = max(dp[i],dp[j]+1)
    for j in road_from[i]:
        dp[j] = max(dp[j],dp[i]+1)

print(max(dp))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    dp = [["" for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                if len(dp[i+1][j]) < len(dp[i][j])+1:
                    if len(dp[i][j+1]) < len(dp[i][j])+1:
                        dp[i+1][j+1] = dp[i][j]+s[i]
                    else:
                        dp[i+1][j+1] = dp[i][j+1]
                else:
                    if len(dp[i+1][j]) > len(dp[i][j+1]):
                        dp[i+1][j+1] = dp[i+1][j]
                    else:
                        dp[i+1][j+1] = dp[i][j+1]
            else:
                if len(dp[i+1][j]) > len(dp[i][j+1]):
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]
    print(dp[len(s)][len(t)])
#G
def G():
    n,m = LI()
    e = LIR(m)
    dp = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)
#H
def H():
    return

#Solve
if __name__ == "__main__":
    G()

Submission status: Wrong Answer

Solution code:
m,n=map(int,input().split())
dp=[[0]*m for i in range(m)]
#me=[[[]*m] for i in range(m)]
he=[[]*m for i in range(m)]
ta=[[]*m for i in range(m)]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if dp[a-1][b-1]==0:
        dp[a-1][b-1]=1
        he[a-1]+=[b-1]
        ta[b-1]+=[a-1]
    a=a-1
    b=b-1
    for j in he[b]:
        dp[a][j]=max(dp[a][j],dp[b][j]+1)
        ans=max(ans,dp[a][j])
    for j in ta[a]:
        dp[j][b]=max(dp[j][b],dp[j][a]+1)
        ans=max(ans,dp[j][b])
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split(" "))
inedge = [0] * N
edge = [ [] for _ in range(N) ]
for i in range(M):
    x,y = map(int,input().split(" "))
    inedge[y-1] += 1
    edge[x-1].append(y-1)

stack = []
for i in range(N):
    if inedge[i] == 0:
        stack.append((i,0))

ans = 0
while len(stack) != 0:
    nextVer,passLen = stack.pop()
    ans = max(ans,passLen)
    for e in edge[nextVer]:
        inedge[e] -= 1
        if inedge[e] == 0:
            stack.append((e,passLen+1))


print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
q=[]
for i in range(n):
    if not oya[i]:
        q.append([i,ko[i]])
while q:
    now,path=q.pop()
    for i in path:
        oya[i].remove(now)
        if not oya[i]:
            rank[i]=max(rank[i],rank[now]+1)
            q.append([i,ko[i]])
print(max(rank))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
q=[]
for i in range(n):
    if not oya[i]:
        q.append([i,ko[i]])
while q:
    now,path=q.pop()
    for i in path:
        oya[i].remove(now)
        if not oya[i]:
            rank[i]=rank[now]+1
            q.append([i,ko[i]])
print(max(rank))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
for s in range(n):
    if not oya[s]:break
q=[]
for i in range(n):
    if not oya[i]:
        q.append([i,ko[i]])
while q:
    now,path=q.pop()
    for i in path:
        oya[i].remove(now)
        if not oya[i]:
            rank[i]=rank[now]+1
            q.append([i,ko[i]])
print(max(rank))

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
edges = [set() for _ in range(N)]
ins = [0]*N
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    ins[b] += 1
    edges[a].add(b)

dp = [0]*N

start = []
for i in range(N):
    if ins[i] == 0:
        start.append(i)


def bfs(s):
    Q = []
    Q.append(s)
    while Q:
        s = Q.pop(0)
        if not edges[s]:
            continue
        else:
            for n in edges[s]:
                dp[n] = dp[s]+1
                Q.append(n)


for s in start:
    bfs(s)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N,M=[int(x) for x in raw_input().split()]
A=[[] for i in range(N)]
B=[[] for i in range(N)]
C=[-1 for i in range(N)]
D=[0 for i in range(N)]
E=[0 for i in range(N)]

for i in range(M):
    a,b=[int(x)-1 for x in raw_input().split()]
    A[a].append(b) #to
    B[b].append(a) #from
F=[]
s=0
for i in range(N):
    D[i]=len(B[i])
    if D[i]==0:
        F.append(i)
        C[i]=0
        for a in A[i]:
            E[a]+=1
        s+=1
level=0
while s<N:
    level+=1
    Fnew=[]
    T=[]
    for f in F:
        for a in A[f]:
            if E[a]==D[a]:
                C[a]=level
                Fnew.append(a)
                s+=1
                for aa in A[a]:
                    T.append(aa)
    F=Fnew[:]
    for aa in T:
        E[aa]+=1
print max(C)

Submission status: Wrong Answer

Solution code:
N,M=[int(x) for x in raw_input().split()]
A=[[] for i in range(N)]
B=[[] for i in range(N)]
C=[-1 for i in range(N)]
D=[0 for i in range(N)]

for i in range(M):
    a,b=[int(x)-1 for x in raw_input().split()]
    A[a].append(b) #to
    B[b].append(a) #from
F=[]
s=0
for i in range(N):
    if len(B[i])==0:
        F.append(i)
        C[i]=0
        D[i]=1
        s+=1
level=0

while s<=N:
    level+=1
    Fnew=[]
    for f in F:
        for a in A[f]:
            for b in B[a]:
                if D[b]==0:
                    break
            else:
                C[a]=level
                D[a]=1
                Fnew.append(a)
                s+=1
    F=Fnew[:]
print max(C)

Submission status: Wrong Answer

Solution code:
N,M=[int(x) for x in raw_input().split()]
A=[[] for i in range(N)]
B=[[] for i in range(N)]
C=[-1 for i in range(N)]
D=[0 for i in range(N)]

for i in range(M):
    a,b=[int(x)-1 for x in raw_input().split()]
    A[a].append(b) #to
    B[b].append(a) #from
F=[]
s=0
for i in range(N):
    if len(B[i])==0:
        F.append(i)
        C[i]=0
        D[i]=1
        s+=1
level=0

for kk in range(10):
    level+=1
    Fnew=[]
    for f in F:
        for a in A[f]:
            for b in B[a]:
                if D[b]==0:
                    break
            else:
                C[a]=level
                D[a]=1
                Fnew.append(a)
                s+=1
    F=Fnew[:]
print max(C)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
inpath = [0] * n
innode = [[] for i in range(n)]
outnode = [[] for i in range(n)]
dp = [0] * n

for i in range(m):
    x, y = map(lambda z:z-1,map(int, input().split())) # 添え字を1~nから0~n-1に調整
    innode[y].append(x)
    outnode[x].append(y)
    inpath[y] += 1
S = []
L = []

for i in range(n):
    if inpath[i] == 0:
        S.append(i) #流入パスがないノードをSに追加

while S: # Sが空でない場合、続ける
    k = S.pop()
    L.append(k)
    for i in outnode[k]:
        inpath[i] -= 1
        if inpath[i] == 0:
            S.append(i)
 
for i in L:
    if not innode[i]: # 流入する辺がない場合    
        dp[i] = 0
    else:
        for j in innode[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(dp[n-1])

Submission status: Wrong Answer

Solution code:
def inpl(): return map(int, input().split())
N, M = inpl()
DP = [0]*(N+1)
for _ in range(M):
    x, y = inpl()
    DP[y] = max(DP[y], DP[x]+1)
print(max(DP))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [[] for i in range(N)] # iからの行き先
Y = [[] for i in range(N)] # iに来る元

for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    X[x].append(y)
    Y[y].append(x)
    
Z = [0 for i in range(N)] # iまでの最長pathの長さ
L = []
k = 0

L.append([])
for i in range(N):
    if len(Y[i]) == 0:
        L[k].append(i)
        Z[i] = 1

while True:
    k += 1
    L.append([])
    for l in L[k-1]:
        for x in X[l]:
            if Z[x] == 0:
                L[k].append(x)
            Z[x] = k + 1
    
    if len(L[k]) == 0:
        print(k-1)
        break

Submission status: Wrong Answer

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
for i in range(N):
    for v in graph_reverse[res[i]]:
        dp[i] = max(dp[i], dp[v]+1)
print(dp[N-1])

Submission status: Wrong Answer

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

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)

def topological_sorted_nodes(i, nexts, prevs):
    visited = [0] * N
    # starting from a middle node.
    for q in prevs[i]:
        visited[q] = 1
    sorted_dist_and_nodes = []
    que = [(0, i)]
    while que:
        dist, p = que.pop(0)
        if not visited[p] and all(visited[q] for q in prevs[p]):
            visited[p] = 1
            sorted_dist_and_nodes.append((dist, p))
            for n in nexts[p]:
                que.append((dist + 1, n))
    return sorted_dist_and_nodes

def max_len(dist_and_nodes, nexts, prevs):
    dp = [0] * N
    for _, p in dist_and_nodes[1:]: # skip the first node.
        for n in prevs[p]:
            dp[p] = max(dp[p], dp[n] + 1)
    return max(dp)

active = set(range(N))
max_dist = 0
while active:
    i = active.pop()
    debug('active', i)
    nodes_fw = topological_sorted_nodes(i, nextnodes[0], nextnodes[1])
    nodes_bw = topological_sorted_nodes(i, nextnodes[1], nextnodes[0])
    d_fw = max_len(nodes_fw, nextnodes[0], nextnodes[1])
    d_bw = max_len(nodes_bw, nextnodes[1], nextnodes[0])
    debug('FW', nodes_fw)
    debug('BW', nodes_bw)
    debug('d', d_fw, d_bw)
    max_dist = max(max_dist, d_fw + d_bw)
    active -= set(p for _, p in nodes_fw)
    active -= set(p for _, p in nodes_bw)

print(max_dist)

Submission status: Wrong Answer

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

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

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 rank[i] == 0:
		dfs(i)

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

Submission status: Wrong Answer

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
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: Wrong Answer

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

dp = [0] * (N+1)
for a,b in es:
    dp[b] = max(dp[b], dp[a]+1)
print(max(dp))

Submission status: Wrong Answer

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:
      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:
temparr = input()
from heapq import heappush, heappop
temparr = temparr.split()
n = int(temparr[0])
edg = int(temparr[1])
dicts = {}
secdict = {}
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 
head = []
for i in range(1, n + 1):
    if i not in secdict:
        heappush(head, (0, i))
maxdist = [0 for _ in range(n + 1)]
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: Time Limit Exceeded

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 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 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())
    print(dag.findLongestPathNaive())


main()

Submission status: Time Limit Exceeded

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):
        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
        for i in range(self.n):
            if not visited[i]:
                self.dfsWithDp(i, dp, visited)
        return max(dp)


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

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):
        visited[node] = True
        for i in range(len(self.adj[node])):
            child = self.adj[node][i]
            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
        for i in range(self.n):
            if not visited[i]:
                self.dfsWithDp(i, dp, visited)
        return max(dp)


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

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)


count = 0
def dfs(v, seen, temp=0):
    global count
    seen[v] = 1
    if to[v]:
        for nv in to[v]:
            dfs(nv, seen, temp + 1)
    else:
        count = max(count, temp)


def main():
    ans = 0
    seen = [0] * N
    for i in range(N):
        if not seen[i]:
            dfs(i, seen)
            ans = max(ans, count)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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)


count = 0
def dfs(v, temp=0):
    global count
    if to[v]:
        for nv in to[v]:
            dfs(nv, temp + 1)
    else:
        count = max(count, temp)


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Start = {a for a in range(N)}
End = set()
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    End.add(y)
Start = Start - End
Q = deque(Start)

DP = [0] * N
ans = 0
while Q:
    now = Q.pop()
    for nex in Edge[now]:
        if DP[nex] < DP[now] + 1:
            DP[nex] = DP[now] + 1
            Q.append(nex)
            ans = max(ans, DP[nex])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Start = {a for a in range(N)}
End = set()
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    End.add(y)
Start = Start - End
Q = deque(Start)

DP = [0] * N
ans = 0
while Q:
    now = Q.pop()
    for nex in Edge[now]:
        if DP[nex] < DP[now] + 1:
            DP[nex] = DP[now] + 1
            Q.append(nex)
            ans = max(ans, DP[nex])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Start = {a for a in range(N)}
End = set()
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    End.add(y)
Start = Start - End
Q = deque(Start)

DP = [0] * N
ans = 0
while Q:
    now = Q.popleft()
    for nex in Edge[now]:
        if DP[nex] < DP[now] + 1:
            DP[nex] = DP[now] + 1
            Q.append(nex)
            ans = DP[nex]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Start = {a for a in range(N)}
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    if y in Start:
        Start.remove(y)

Q = deque(Start)

DP = [0] * N

while Q:
    now = Q.popleft()
    for nex in Edge[now]:
        if DP[nex] < DP[now] + 1:
            DP[nex] = DP[now] + 1
            Q.append(nex)
print(max(DP))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
n, m = map(int, input().split())
From = defaultdict(list)
To = defaultdict(bool)

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


q = deque()
for i in range(n):
    if not To[i]:
        q.append((i, 1))

dist = [0]*n

while q != deque():
    p, cnt = q.popleft()
    for t in From[p]:
        q.append((t, cnt+1))
        dist[t] = max(dist[t], cnt)

print(max(dist))

Submission status: Time Limit Exceeded

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

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

def dfs(pos):
    if not edges[pos]:
        dp[pos] = 0
        return
    for n_pos in edges[pos]:
        if not used[n_pos]:
            dfs(n_pos)
        dp[pos] = max(dp[pos], dp[n_pos] + 1)
        

for i in range(n):
    if used[i]:
        continue
    used[i] = True
    dfs(i)
    
print(max(dp))

Submission status: Time Limit Exceeded

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

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

def dfs(pos):
    if not edges[pos]:
        dp[pos] = 0
        return
    for n_pos in edges[pos]:
        if not used[n_pos]:
            dfs(n_pos)
        dp[pos] = max(dp[pos], dp[n_pos] + 1)

for i in range(n):
    if used[i]:
        continue
    used[i] = True
    dfs(i)
    
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import queue
n, m = map(int, input().split())
a = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    a[x-1].append(y)
ans = 0
for i in range(n):
    q = queue.Queue()
    q.put([i])
    while not q.empty():
        c = q.get()
        for j in a[c[-1]]:
            if j-1 in c:
                continue
            else:
                q.put(c+[j-1])
        ans = max(len(c), ans)
print(ans-1)

Submission status: Time Limit Exceeded

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

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)
dp = [-1]*n
    
def calc(x):
    if dp[x] != -1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max(calc(i) for i in edge[x])+1
    return dp[x]
    
ans = 0
for i in range(n):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)

Submission status: Time Limit Exceeded

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

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)
dp = [-1]*n
    
def calc(x):
    if dp[x] != -1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max(calc(i) for i in edge[x])+1
    return dp[x]
    
ans = 0
for i in range(n):
    ans = max(ans, calc(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
N,M=map(int, input().split())
G = {i: [] for i in range(1, N+1)}
for _ in range(M):
    x,y=map(int,input().split())
    G[x].append(y)

dp = [-1]*(N+1)
for s in range(1, N+1):
    if dp[s] != -1:
        continue
    que = deque([s])
    dp[s] = 0
# for node in range(1, N+1):
#     for nx in G[node]:
#         dp[nx] = max(dp[nx], dp[node]+1)
    while que:
        node = que.popleft()
        for nx in G[node]:
            dp[nx] = max(dp[nx], dp[node]+1)
            que.append(nx)
        
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF=float('inf')

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

ans=-INF
for i in range(n):
  dist=[-INF for _ in range(n)]
  Q=[(0,i)]
  dist[i]=0
  heapq.heapify(Q)
  while Q:
    d,v=heapq.heappop(Q)
    for nv in adj[v]:
      if dist[nv]<dist[v]+1:
        dist[nv]=dist[v]+1
        heapq.heappush(Q,(dist[nv],nv))
  ans=max(ans,max(dist))
  
print(ans)

Submission status: Time Limit Exceeded

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

def longest_path(s):
    global dp
    if adj[s]:
        dp[s-1]=max((longest_path(t)+1)for t in adj[s])
    else:
        dp[s-1]=0
    return dp[s-1]

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

adj={}
for n in range(1,N+1):
    l=[]
    for m in range(M):
        if edge[m][0]==n:
            l.append(edge[m][1])
    adj[n]=l

dp=[0]*N
for i in range(1,N+1):
    if dp[i-1]==0:
        longest_path(i)

print(max(dp))