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
sys.setrecursionlimit(100000)

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

dp = [-1 for _ in range(N+1)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    
    paths = 0
    for _, t in filter(lambda x: x[0] == i, links):
        paths = max(paths, search(t)+1)
    
    dp[i] = paths
    return paths

for i in range(1, N+1):
    search(i)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
links = [list(map(int, input().split())) for _ in range(M)]

dp = [-1 for _ in range(N+1)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    
    paths = 0
    for _, t in filter(lambda x: x[0] == i, links):
        paths = max(paths, search(t)+1)
    
    dp[i] = paths
    return paths

for i in range(1, N+1):
    search(i)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)


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

e_list = [[] for i in range(N)]

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

from functools import lru_cache

@lru_cache(maxsize=N*10)
def DFS(v):
    if len(e_list[v])==0:
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)


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

e_list = [[] for i in range(N)]

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

from functools import lru_cache

@lru_cache(maxsize=N)
def DFS(v):
    if len(e_list[v])==0:
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
IN = [0]*N
A = list()
B = list()
TOP = list()
sum = 0
for i in range(M):
    x,y = map(int,input().split())
    IN[y-1] += 1
    A.append(x)
    B.append(y)
#print("A:", A, "B:", B, "IN:", IN, "TOP:", TOP)

#while 0 in IN:
#    E = IN.index(0)
#    TOP.append(E+1)
#    IN[E] -= 1
#    while E+1 in A:
#        IN[B[A.index(E+1)]-1] -= 1
#        A[A.index(E+1)] = 0
#print("A:", A, "B:", B, "IN:", IN, "TOP:", TOP)


while 0 in IN:
    E = [i for i, x in enumerate(IN) if x == 0]
    for i in range(len(E)):
        TOP.append(E[i]+1)
        IN[E[i]] -= 1
        while E[i]+1 in A:
            IN[B[A.index(E[i]+1)]-1] -= 1
            A[A.index(E[i]+1)] = 0
        if i != 0:
            sum += 1

#print("A:", A, "B:", B, "IN:", IN, "TOP:", TOP)
#print("sum:", sum)
print(N-1-sum)

Submission status: Time Limit Exceeded

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

dp = [-1] * N


def rec(v):
    if dp[v] >= 0:
        return dp[v]
    if len(G[v]) == 0:
        return 0

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

    return ret


print(max([rec(v) for v in range(N)]))

Submission status: Time Limit Exceeded

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

def main():
    N,M = map(int,input().split())
    
    edge = [[] for _ in range(N)]
    begin = [True for _ in range(N)]
    for _ in range(M):
        x,y = map(int,input().split())
        edge[x-1].append(y-1)
        begin[y-1] = False
            
    def longest(s):
        INF = 10**10
        l = [-INF for _ in range(N)]
        l[s] = 0
        q = deque([s])
        while q:
            now = q.popleft()
            for fol in edge[now]:
                if l[fol] < l[now]+1:
                    l[fol] = l[now]+1
                    q.append(fol)
        return max(l)
    
    ans = 0
    for i,b in enumerate(begin):
        if b:
            ans = max(ans,longest(i))
            
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
int1 = lambda x: int(x) - 1
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

start_point = set(range(N))
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    start_point = start_point - {y}
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

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

print(max(dp_memo))

Submission status: Time Limit Exceeded

Solution code:
int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

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

start_point = set(range(N))
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    start_point = start_point - {y}
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

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

print(max(dp_memo))

Submission status: Time Limit Exceeded

Solution code:
int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

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

start_point = set(range(N))
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    start_point = start_point - {y}
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

ans = 0
for x in start_point:
    ans = max(ans, dp(x))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

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

edge = [[0]*N for _ in range(N)]
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    edge[x][y] += 1
    to_point[x].append(y)

end_point = set()
for x in range(N):
    if len(to_point[x]) == 0:
        end_point.add(x)

start_point = set()
for y in range(N):
    for x in range(N):
        if edge[x][y] > 0:
            break
    else:
        start_point.add(y)

dp_memo = [-1]*N

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    if i in end_point:
        dp_memo[i] = 0
        return 0
    else:
        lp = 0
        for j in to_point[i]:
            lp = max(lp, dp(j)+1)
        dp_memo[i] = lp
        return lp

ans = 0
for x in start_point:
    ans = max(ans, dp(x))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

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

edge = [[0]*N for _ in range(N)]
to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    edge[x][y] += 1
    to_point[x].append(y)

end_point = set()
for x in range(N):
    if len(to_point[x]) == 0:
        end_point.add(x)

start_point = set()
for y in range(N):
    for x in range(N):
        if edge[x][y] > 0:
            break
    else:
        start_point.add(y)

# 点i始点のLongest Pathの長さ
def dp(i):
    if i in end_point:
        return 0
    else:
        lp = 0
        for j in to_point[i]:
            lp = max(lp, dp(j)+1)
        return lp

ans = 0
for x in start_point:
    ans = max(ans, dp(x))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

N, M = map(int, input().split())
edge = [[0]*N for _ in range(N)]
for _ in range(M):
    x, y = map(int1, input().split())
    edge[x][y] += 1

end_point = set()
for x in range(N):
    for y in range(N):
        if edge[x][y] > 0:
            break
    else:
        end_point.add(x)

start_point = set()
for y in range(N):
    for x in range(N):
        if edge[x][y] > 0:
            break
    else:
        start_point.add(y)

# 点i始点のLongest Pathの長さ
def dp(i):
    if i in end_point:
        return 0
    else:
        lp = 0
        for j, flg in enumerate(edge[i]):
            if flg > 0:
                lp = max(lp, dp(j)+1)
        return lp

ans = 0
for x in start_point:
    ans = max(ans, dp(x))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
dp = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    path[x-1].add(y-1)
    dp[y-1] = -1

que = deque()
for i in range(n):
    if dp[i] == 0:
        que.append(i)
ans = 0
while que:
    p = que.popleft()
    for i in path[p]:
        que.append(i)
        dp[i] = max(dp[i], dp[p] + 1)
        ans = max(ans, dp[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = 0
    for b in xy[a]:
      num = cal(b)
      dp[b] = num
      if num+1 > ans:
        ans = num+1
    return ans
  return 0

if __name__ == "__main__":
  sys.setrecursionlimit(100000)
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()

Submission status: Time Limit Exceeded

Solution code:
inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if not x in g.keys():
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    if not x in g.keys():
        g[x] = []
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
path = [0 for i in range(n+1)]
for a,b in ab:
  graph[b].append(a)
  path[a] = -1
stack = []
for i in range(1,n+1):
  if path[i] == 0:
    stack.append(i)
    while stack:
      x = stack.pop()
      for y in graph[x]:
        if path[x]+1 > path[y]:
          stack.append(y)
          path[y] = path[x]+1
print(max(path))

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N, M = map(int, input().split())
    g = [[] for _ in range(N)] #場合によって変える
    
    for _ in range(M):
        x, y = map(int, input().split())
        g[x-1].append(y-1)
    dp = [0]*N
    
    def func(i):
        for j in g[i]:
            dp[j] = max(dp[j], dp[i]+1)
            func(j)

    for i in range(N):
        if dp[i]==0:
            func(i)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
G=[set() for i in range(N)]
IN = [0 for i in range(N)]
for _ in range(M):
    x,y=map(int,input().split())
    G[x-1].add(y-1)
    IN[y-1]+=1
T=[]
while len(T)<N:
    for i in range(N):
        if IN[i]==0:
            IN[i]=-1
            T.append(i)
            for v in G[i]:
                IN[v]-=1
dp=[0 for i in range(N)]
dp[T[N-1]]=0
for i in range(1,N):
    j=N-1-i
    n=[]
    for k in G[T[j]]:
        n.append(dp[k])
    if len(n)!=0:
        dp[T[j]]=max(n)+1
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**9)

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

g = [[] for i in range(n)]

for _ in range(m):
  v1 , v2 = map(int,input().split())
  v1 -=1; v2 -=1
  g[v1].append(v2)
  
# finding longest path for vertice i
def dfs(i):
  temp = 0
  for nv in g[i]:
    temp = max(temp, dfs(nv)+1)
    
  return temp
  
# finding overall longest path  
res = 0  
for i in range(n):
  res = max(res, dfs(i))
  
print(res)

Submission status: Time Limit Exceeded

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

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

dp = [-1] * N
def dfs(v, dist):
    for i in path[v]:
        dp[v] = max(dp[v], dfs(i, dist+1))
    return dist

for i in range(N):
    if dp[i] < 0:
        dfs(i, 0)

print(max(dp))

Submission status: Time Limit Exceeded

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

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

dp = [0] * N
def dfs(v, dist):
    for i in path[v]:
        dp[v] = max(dp[v], dfs(i, dist+1))
    return dist

for i in range(N):
    dfs(i, 0)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(M)]

from collections import defaultdict
from collections import deque
g = defaultdict(set)

for x, y in XY:
  g[x].add(y)

  
def bfs(u):
  s = deque([u])
  cost = {u: 0}
  done = set()
  while s:
    u = s.popleft()
    if u not in done:
      done.add(u)
    else:
      continue
    for v in g[u]:
      cost[v] = cost[u] + 1
      if v in done:
        done.remove(v)
      s.append(v)

  return cost
  
ans = 0
for i in range(1, N+1):
  d = bfs(i)
  ans = max(ans, max(d.values()))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(M)]

from collections import defaultdict
from collections import deque
g = defaultdict(set)

for x, y in XY:
  g[x].add(y)

  
def bfs(u):
  s = deque([u])
  done = {u: 0}
  while s:
    u = s.popleft()
    for v in g[u]:
      done[v] = done[u] + 1
      s.append(v)
  return done
  
ans = 0
for i in range(1, N+1):
  d = bfs(i)
  ans = max(ans, max(d.values()))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        src, dst = map(int, input().split())
        graph[dst].append(src)

    dist = [0] * (n+1)
    for node in range(1, n+1):
        visited = [False] * (n+1)
        q = deque([node])
        while q:
            at = q.popleft()
            visited[at] = True
            for to in graph[at]:
                dist[to] = max(dist[to], dist[at] + 1)
                if not visited[to]:
                    q.append(to)
    print(max(dist[1:]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def bell(edges, n):
    dist = [0 for i in range(n)]
 
    changed = True
 
    while changed:
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + 1:
                changed = True
                dist[edge[1]] = max(dist[edge[0]] + 1, dist[edge[1]])
                
    return dist
 
 
n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b= (int(x) for x in input().split())
    edges.append([a-1, b-1])
 
res = bell(edges, n)
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
# input
N, M = map(int, input().split())
edges = []
for i in range(M):
  edges.append(list(map(int, input().split())))

# DP
cost = [[float(0)] * N for i in range(N)]

for e in edges:
  e[0] -= 1
  e[1] -= 1
  cost[e[0]][e[1]] = 1

for e in edges:
  for i in range(N):
    if cost[i][e[0]] > 0: # i → e.start への経路があるとき
      cost[i][e[1]] = max(cost[i][e[1]], cost[i][e[0]] + 1)
  for j in range(N):
    if cost[e[1]][j] > 0: # e.end → j への経路があるとき
      cost[e[0]][j] = max(cost[e[0]][j], cost[e[1]][j] + 1)

ans = 0
for i in range(N):
  for j in range(N):
    if ans < cost[i][j]:
      ans = cost[i][j]

print(ans)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
dp = [-1 for _ in range(n)]

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


def dfs(s):
    #print(s, dp)
    if dp[s] != -1:
        return dp[s]
    
    rep = 0
    for g in graph[s]:
        rep = max(rep, dfs(g)+1)
    dp[s] = rep
    return rep

def dfs2(s):
    rep = 0
    for g in graph[s]:
        rep = max(rep, dfs2(g)+1)
    #print(rep)
    return rep

#print(graph)
ans = 0
for i in range(n):
    #print('i:', i)
    ans = max(ans, dfs2(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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

def dfs(v):
    dist = [-1] * n
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in g[v]:
            dist[w] = dw
            stack.append(w)
    return max(dist)

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

Submission status: Time Limit Exceeded

Solution code:
# input
N, M = map(int, input().split())
cost = [[float('inf')] * N for i in range(N)]

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

for i in range(N):
  for j in range(N):
    for k in range(N):
      cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

ans = 0
for i in range(N):
  for j in range(N):
    if ans > cost[i][j]:
      ans = cost[i][j]

print(ans * -1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

    @lru_cache(maxsize=None)
    def dfs(v, par=-1):
        """最長有向パスに含まれる頂点数"""
        ret = 0
        for u in g[v]:
            if u == par: continue
            ret = max(ret, dfs(u, v))
        return ret + 1

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

    g = tuple(set() for _ in range(n))
    for _ in range(m):
        x, y = (int(c) - 1 for c in input().split())
        g[x].add(y)

    ret = 0
    for i in range(n):
        ret = max(ret, dfs(i))
    print(ret - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n,m = map(int, input().split())
G = [[] for i in range(n)]

in_ = set()
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    in_.add(b)

dist = [-1]*n

from collections import deque
def dfs(cur):
    que = deque()
    que.append((cur, 0))
    while que:
        cur, d = que.pop()
        if dist[cur] > d:
            continue
        dist[cur] = d
        for to in G[cur]:
            if dist[to] < d+1:
                que.append((to, d+1))

for i in range(n):
    if i in in_:
        continue
    dfs(i)

ans = max(dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=deque(s)
    memo=[0]*N
    ans=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            memo[nv]=max(memo[nv],memo[v]+1)
            ans=max(ans,memo[nv])
            que.append(nv)
    print(ans)
    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))
move.sort(key=itemgetter(0))

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

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    for x,y in move:
        if now_x == x:
            maxpath = max(maxpath,findpath(y) + 1)
        if now_x < x:
            break
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))
move.sort(key=itemgetter(0))

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

def findpath(now_x):
    if now_x <= done_n:
        return dp[now_x]
    for x,y in move:
        if now_x == x:
            dp[now_x] = max(dp[now_x],findpath(y) + 1)
        if now_x < x:
            break
    return dp[now_x]

maxpath = 0
for do_n in range(1,N+1):
    done_n = do_n - 1
    maxpath = max(maxpath,findpath(do_n))

print(maxpath)

Submission status: Time Limit Exceeded

Solution code:
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))

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

def findpath(now_x):
    if now_x <= done_n:
        return dp[now_x]
    for x,y in move:
        if now_x == x:
            dp[now_x] = max(dp[now_x],findpath(y) + 1)
    return dp[now_x]

maxpath = 0
for do_n in range(1,N+1):
    done_n = do_n - 1
    maxpath = max(maxpath,findpath(do_n))

print(maxpath)

Submission status: Time Limit Exceeded

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

C=[[0]*N for i in range(N)]

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

f=True
mx=1
while f:
    f=False
    for i in range(N):
        for j in range(N):
            if C[i][j]!=0:
                for k in range(N):
                    if C[j][k]!=0:
                        if C[i][j]+C[j][k]>C[i][k]:
                            C[i][k]=C[i][j]+C[j][k]
                            f=True
                        mx=max(mx,C[i][k])

print(mx)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline  #文字列入力では注意！
from copy import deepcopy
from functools import lru_cache
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
s = set()
for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    s.add(y)
    graph[x].append(y)

@lru_cache(maxsize = None)
def dfs(x):
    if not graph[x]:
        return 0
    stack = deepcopy(graph[x])
    ret = 0
    while stack:
        now = stack.pop(0)
        ret = max(ret,dfs(now)+1)
    return ret

ans = 0
for i in range(N):
    if i not in s:
        ans = max(ans,dfs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline  #文字列入力では注意！
from copy import deepcopy

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

def dfs(x):
    #print(x,graph[x])
    if not graph[x]:
        return 0
    stack = deepcopy(graph[x])
    ret = 0
    while stack:
        now = stack.pop(0)
        ret = max(ret,dfs(now)+1)
    return ret

ans = 0
for i in range(N):
    if i not in s:
        ans = max(ans,dfs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
G=[[] for i in range(n+1)]
flag=[1]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    G[x].append(y)
    flag[y]=0
# dp[i] node iからの最長パス
dp=[-1]*(n+1)
st=[]
for i in range(1,n+1):
    if flag[i]:
        st.append(i)
ans=0

def dfs(x):
    max_kyori=0
    dist=[-1]*(n+1)
    dist[x]=0
    stack=[x]
    while stack:
        a=stack.pop()
        kyori = dist[a]
        if G[a]!=[]:
            for t in G[a]:
                dist[t]=kyori+1
                max_kyori=max(max_kyori,kyori+1)
                stack.append(t)
    return max_kyori
kotae=0
for i in st:
    kotae=max(kotae,dfs(i))
print(kotae)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
G=[[] for i in range(n+1)]
flag=[1]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    G[x].append(y)
    flag[y]=0
# dp[i] node iからの最長パス
dp=[-1]*(n+1)
st=[]
for i in range(1,n+1):
    if flag[i]:
        st.append(i)
ans=0

def dfs(x):
    max_kyori=0
    dist=[-1]*(n+1)
    dist[x]=0
    stack=[x]
    while stack:
        a=stack.pop()
        kyori = dist[a]
        if G[a]!=[]:
            for t in G[a]:
                dist[t]=kyori+1
                max_kyori=max(max_kyori,kyori+1)
                stack.append(t)
    return max_kyori
kotae=0
for i in st:
    kotae=max(kotae,dfs(i))
print(kotae)

Submission status: Time Limit Exceeded

Solution code:
def solve(N, M, edges):
  inbound = {}
  for s,t in edges:
    if t in inbound:
      inbound[t].append(s)
    else:
      inbound[t] = [s]

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

  for s,t in edges:
    dp[s][t] = 1

  max_so_far = 0
  for i in range(1, N + 1):
    for s in range(1, N + 1):
      for t in range(1, N + 1):
        t_inbound = inbound[t] if t in inbound else []
        for t_i in t_inbound:
          # dp[s][t] = max(dp[s][t], dp[s][t_i] + 1)
          # max_so_far = max(max_so_far, dp[s][t])
          temp = dp[s][t_i] + 1
          if temp > dp[s][t]:
            dp[s][t] = temp
          if temp > max_so_far:
            max_so_far = temp

  print(max_so_far)


def iln(): return list(map(int, input().split()))


N, M = iln()
edges = []
for i in range(M):
  edges.append(iln())
  
solve(N, M, edges)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M = map(int, input().split())
t_table = {}
for i in range(M):
	x,y = map(int, input().split())
	if x-1 in t_table: t_table[x-1].append(y-1)
	else: t_table[x-1] = [y-1]
ans = 0
dp = [1 for _ in range(N)]
zerolist = [0 for _ in range(N)]
while True:
	pnode = copy.copy(dp)
	dp = [0 for _ in range(N)]
	for i in range(N):
		if pnode[i] == 1 and i in t_table:
			for j in t_table[i]:
				if dp[j]==0 : dp[j]= 1
	if(dp == zerolist):
	 	print(ans)
	 	break
	ans += 1

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
t_table = {}
for i in range(M):
	x,y = map(int, input().split())
	if x-1 in t_table: t_table[x-1].append(y-1)
	else: t_table[x-1] = [y-1]
ans = 0
dp = [1 for _ in range(N)]
zerolist = [0 for _ in range(N)]
while True:
	pnode = dp.copy()
	dp = [0 for _ in range(N)]
	for i in range(N):
		if pnode[i] == 1 and i in t_table:
			for j in t_table[i]:
				if dp[j]==0 : dp[j]= 1
	if(dp == zerolist):
	 	print(ans)
	 	break
	ans += 1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M = map(int, input().split())
t_table = {}
for i in range(M):
	x,y = map(int, input().split())
	if x-1 in t_table: t_table[x-1].append(y-1)
	else: t_table[x-1] = [y-1]
ans = 0
dp = np.ones(N, dtype='int32')
while True:
	pnode = dp.copy()
	dp = np.zeros(N, dtype='int32')
	for i in np.where(pnode)[0]:
		if i in t_table :
			dp[t_table[i]] += 1
	dp[dp>0] = 1
	if((dp == 0).all()):
	 	print(ans)
	 	break
	ans += 1