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:
def main():
    import sys
    input = sys.stdin.readline

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

    setXY = set(XY)

    calc_set = set([])
    dist_list = [0]*N

    for i in range(N):
        search_list = [i]
        visited = set([])
        dp = [0]*N
        if i in calc_set:
            dp[0] = dist_list[i]
        else:
            while search_list:
                s = search_list.pop()
                visited.add(s)
                for new_s in range(N):
                    if str([s+1, new_s+1]) in setXY:
                        if new_s in search_list:
                            dp[new_s] = max(dp[new_s], 1+dp[s])
                            continue
                        elif new_s in visited:
                            dp[new_s] = max(dp[new_s], 1+dp[s])
                            continue
                        elif new_s in calc_set:
                            dp[new_s] = dist_list[new_s] + 1
                            continue
                        else:
                            dp[new_s] = 1 + dp[s]
                            search_list.append(new_s)
            # print('tmp', dp)
        calc_set.add(i)
        dist_list[i] = max(dp)
    # print(dist_list)
    print(max(dist_list))
    # for xy in XY:
    #     x, y = xy
    #     pass

    # setXY = set(XY)
    # for i in range(N):
    #     for j in range(N):
    #         if str([i+1, j+1]) in setXY:
    #             dp[i][j] = 1
    #         # else:
    #         #     dp[i][j] = min(dp[i][j])
    # print(dp)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    setXY = set(XY)

    calc_set = set([])
    dist_list = [0]*N

    for i in range(N):
        search_list = [i]
        visited = set([])
        dp = [0]*N
        while search_list:
            s = search_list.pop()
            visited.add(s)
            for new_s in range(N):
                if str([s+1, new_s+1]) in setXY:
                    if new_s in search_list:
                        dp[new_s] = max(dp[new_s], 1+dp[s])
                        continue
                    elif new_s in visited:
                        dp[new_s] = max(dp[new_s], 1+dp[s])
                        continue
                    elif new_s in calc_set:
                        dp[new_s] = dist_list[new_s] + 1
                        continue
                    else:
                        dp[new_s] = 1 + dp[s]
                        search_list.append(new_s)
        # print('tmp', dp)
        calc_set.add(i)
        dist_list[i] = max(dp)
    # print(dist_list)
    print(max(dist_list))
    # for xy in XY:
    #     x, y = xy
    #     pass

    # setXY = set(XY)
    # for i in range(N):
    #     for j in range(N):
    #         if str([i+1, j+1]) in setXY:
    #             dp[i][j] = 1
    #         # else:
    #         #     dp[i][j] = min(dp[i][j])
    # print(dp)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split(' '))
dp = [0 for _ in range(N + 1)]
root = [[0 for _ in range(2)] for _ in range(M)]
for i in range(M):
  a, b = map(int, input().split(' '))
  root[i] = [a, b]
root.sort(key=lambda x: x[0])
for _ in range(M):
  for item in root:
    dp[item[1]] = max(dp[item[0]] + 1, dp[item[1]])
print(max(dp))

Submission status: Time Limit Exceeded

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

done = []
def dfs(i):
    if i in done:
        done.pop()
        if dp[i] < len(done):dp[i] = len(done)
        return len(done)
    for j in graph[i]:
        if not(j in done):
            done.append(i)
            dfs(j)
    if dp[i] < len(done):dp[i] = len(done)
    if done:done.pop()
    return len(done)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
route = [[False for x in range(n+1)] for x in range(n+1)]
ans = [-1 for x in range(n+1)]
start = set(range(1,n+1))
q = deque()
for i in range(m):
    x,y = map(int,input().split())
    route[x][y] = True
    start.discard(y)
for start_point in start:
    ans[start_point] = 0
    for end_point in range(1,n+1):
        if(route[start_point][end_point]):
            q.append((start_point,end_point))
while(len(q) > 0):
    start_point,end_point = q.popleft()
    ans[end_point] = max(ans[end_point],ans[start_point]+1)
    for i in range(1,n+1):
        if(route[end_point][i]):
            
            q.append((end_point,i))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
route = [[False for x in range(n+1)] for x in range(n+1)]
ans = [-1 for x in range(n+1)]
start = set(range(1,n+1))
q = deque()
for i in range(m):
    x,y = map(int,input().split())
    route[x][y] = True
    start.discard(y)
for start_point in start:
    ans[start_point] = 0
    for end_point in range(1,n+1):
        if(route[start_point][end_point]):
            q.append((start_point,end_point))
while(len(q) > 0):
    start_point,end_point = q.popleft()
    ans[end_point] = max(ans[end_point],ans[start_point]+1)
    for i in range(1,n+1):
        if(route[end_point][i]):
            q.append((end_point,i))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N,M = LI()
root = [[] for _ in range(N+1)]
dp = [-1 for _ in range(N+1)]
for _ in range(M):
    x,y = LI()
    root[x].append(y)

q = []

for i in range(1,N+1):
    if dp[i] >= 0: continue
    q.append((i,0))
    while q:
        x,d = q.pop()
        dp[x] = d
        for y in root[x]:
            if dp[y] < d+1:
                q.append((y,d+1))

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N,M = LI()
root = [[] for _ in range(N+1)]
dp = [-1 for _ in range(N+1)]
for _ in range(M):
    x,y = LI()
    root[x].append(y)

q = collections.deque()

for i in range(1,N+1):
    if dp[i] >= 0: continue
    q.append((i,0))
    while q:
        x,d = q.popleft()
        dp[x] = d
        for y in root[x]:
            if dp[y] < d+1:
                q.append((y,d+1))

print(max(dp))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
se=set()
d=defaultdict(int)
for i in range(M):
    x,y=map(int,input().split(' '))
    se.add(x*(10**5)+y)
n=set(i for i in range(1,N+1))
while N>0:
    m=set([x%10**5 for x in se])
    for i in n-m:
        n.remove(i)
        N-=1
        de=set([x for x in se if x//10**5==i])
        for j in de:
            k=j%10**5
            se.remove(j)
            if d[k]<=d[i]:
                d[k]=d[i]+1
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
d=defaultdict(int)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    for i in n-set(y):
        n.remove(i)
        for j in range(M):
            if i==x[j]:
                if d[y[j]]<=d[i]:
                    d[y[j]]=d[i]+1
                y[j]=0
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
se=set()
d=defaultdict(int)
for i in range(M):
    x,y=map(int,input().split(' '))
    se.add(x*(10**5)+y)
n=set(i for i in range(1,N+1))
while N>0:
    m=set([x%10**5 for x in se])
    for i in n-m:
        n.remove(i)
        N-=1
        de=[x for x in se if x//10**5==i]
        for j in de:
            k=j%10**5
            se.remove(j)
            if d[k]<=d[i]:
                d[k]=d[i]+1
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
d=defaultdict(int)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    m=n-set(y)
    for i in m:
        n.remove(i)
        for j in range(M):
            if i==x[j]:
                if d[y[j]]<=d[i]:
                    d[y[j]]=d[i]+1
                y[j]=0
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
z=[0]*(N+1)
key=[0]*(N+1)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    for i in n-set(y):
        n.remove(i)
        for j in range(M):
            if i==x[j]:
                if z[y[j]]<=z[x[j]]:
                    z[y[j]]=z[x[j]]+1
                x[j],y[j]=0,0
print(max(z))

Submission status: Time Limit Exceeded

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
z=[0]*(N+1)
key=[0]*(N+1)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    for i in n:
        if i not in y:
            n.remove(i)
            for j in range(M):
                if i==x[j]:
                    if z[y[j]]<=z[x[j]]:
                        z[y[j]]=z[x[j]]+1
                    x[j],y[j]=0,0
            break
print(max(z))

Submission status: Time Limit Exceeded

Solution code:
#DAGの最長有向パスをトポロジカルソートで解く
N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
z=[0]*(N+1)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=[i for i in range(1,N+1)]
while len(n)>0:
    for i in n:
        if i not in y:
            n.remove(i)
            for j in range(M):
                if i==x[j]:
                    if z[y[j]]<=z[x[j]]:
                        z[y[j]]=z[x[j]]+1
                    x[j],y[j]=0,0
            break
print(max(z))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  start.discard(y-1)

mem = [None for n in range(N)]
q = list(start)
for i in q : mem[i] = 0

longest = 0
while q :
  cur = q.pop()
  for nxt in gra[cur] :
    mem[nxt] = mem[cur] + 1
    longest = max(longest, mem[nxt])
    q.append(nxt)

print longest

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


n,m=mdata()
dp=[0]*n
g=[set() for i in range(n)]
par=[i for i in range(n)]
for i in range(m):
    x,y=mdata()
    g[x-1].add(y-1)
for i in range(n):
    if par[i]==i:
        s1=set()
        s1.add(i)
        while s1:
            s2=set()
            for i in s1:
                for j in g[i]:
                    s2.add(j)
                    dp[j]=max(dp[j],dp[i]+1)
            s1=s2.copy()
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import csgraph_from_dense, bellman_ford
import numpy as np

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


def main():
    N, M = map(int, input().split())
    G = [[0 for i in range(N)] for j in range(N)]

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

    G = csgraph_from_dense(G, null_value=0)
    d = bellman_ford(G)

    print(int(-min(d.flatten())))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#input
N, M = map(int, input().split())
x, y = [0]*M, [0]*M
for i in range(M):
    x[i], y[i] = map(int, input().split())

#output
#便宜的にすべての点を-1しておく。
#dp[i]を頂点iから始まるpathで最長の長さとする。
#dp[i] = max(dp[v]+1)(vは頂点iから到達できる任意の頂点)
z = [[]] * N
for xitem in x:
    z[xitem-1] = [yitem-1 for i, yitem in enumerate(y) if x[i] == xitem]

visited = [False] * N
memo = [0] * N
dp = [0] * N

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in z[v]:
            res = max(res, dp(u)+1)
        memo[v] = res
        visited[v] = True
        return res
for i in range(N):
    dp(i)

print(max(memo))

Submission status: Time Limit Exceeded

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

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

memo = [-1]*n

def dp(v):
    if memo[v] >= 0:
        return memo[v]
    else:
        res = 0
        for u in g[v]:
            res = max(res, dp(u) + 1)
        return res

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

Submission status: Time Limit Exceeded

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

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

memo = [-1]*n

def dp(v):
    if memo[v] >= 0:
        return memo[v]
    else:
        res = 0
        for u in g[v]:
            res = max(res, dp(u) + 1)
        return res
ans = -1
for i in range(n):
    ans = max(ans, dp(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N, M = map(int, input().strip().split())
    E_out = [list() for i in range(N)]
    E_in = [list() for i in range(N)]
    for i in range(M):
        x, y = map(int, input().strip().split())
        E_out[x-1].append(y-1)  # x -> E_out[x]
        E_in[y-1].append(x-1)   # E_in[x] -> x
    return N, M, E_in, E_out


def solve(N, M, E_in, E_out):
    dp = [-1 for i in range(N)]
    q = deque()
    for x in range(N):
        if len(E_out[x]) == 0:
            q.append(x)
            dp[x] = 0
    while q:
        x = q.pop()
        for y in E_in[x]:
            q.append(y)
            dp[y] = max(dp[y], dp[x] + 1)
    return max(dp)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(x) for x in input().split()]
g = [[]*n for _ in range(n)]
visited = set()
for _ in range(m):
    x, y = [int(x) for x in input().split()]
    g[x - 1].append(y - 1)
dp = [0] * n
from collections import deque
def dfs(u):
    queue = deque([u])
    d = [None]*n
    max_d = 0
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                max_d = max(max_d, d[i])
                queue.append(i)
                visited.add(i)
            elif d[v] + 1 >= d[i]:
                d[i] = max(d[i], d[v] + 1)
                max_d = max(max_d, d[i])
                queue.append(i)
    return max_d

for i in range(n):
    if i in visited:
        continue
    dp[i] = dfs(i)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n, m = map(int, input().split())
  tree_to = [[] for _ in range(n)]
  tree_from = [[] for _ in range(n)]
  for i in range(m):
    x, y = map(int, input().split())
    tree_to[x-1].append(y-1)
    tree_from[y-1].append(x-1)
  
  ans = [0]*n
  already = [False]*n
  for i in range(n):
    if already[i]:
      continue
    already[i] = True
    not_yet = deque(tree_to[i])
    while not_yet:
      key = not_yet.pop()
      if ans[key] or not tree_to[key]:
        already[key] = True
        search = deque(tree_from[key])
        while search:
          already[i]
          sub = search.popleft()
          ans[sub] = 1
          for v in tree_to[sub]:
            if ans[sub] < ans[v]+1:
              ans[sub] = ans[v]+1
          for v in tree_from[sub]:
            search.append(v)
        continue
      for v in tree_to[key]:
        not_yet.append(v)
  print(max(ans))
      

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

from collections import defaultdict

# from typing import Dict, List, Optional, Set, Tuple


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, nb_edges) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = {s: True for s in succ}
    empty_dp = {s: False for s in succ}
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = empty_dp.copy()
        # vertices are indexed from 1
        for vertex in succ:
            for d in succ[vertex]:
                if prev.get(d - 1, False):
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


if __name__ == "__main__":
    do_job()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

# from typing import Dict, List, Optional, Set, Tuple


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, nb_edges) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = {s: True for s in succ}
    empty_dp = {s: False for s in succ}
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = empty_dp.copy()
        # vertices are indexed from 1
        for vertex in succ:
            for d in succ[vertex]:
                if prev.get(d - 1, False):
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


def main():
    "Program wrapper."
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

# from typing import Dict, List, Optional, Set, Tuple


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, nb_edges) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = {s: True for s in succ}
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = {s: False for s in succ}
        # vertices are indexed from 1
        for vertex in succ:
            for d in succ[vertex]:
                if prev.get(d - 1, False):
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


def main():
    "Program wrapper."
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

# from typing import Dict, List, Optional, Set, Tuple


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, nb_vertices, nb_edges) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = [True] * nb_vertices
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = [False] * nb_vertices
        # vertices are indexed from 1
        for vertex in range(1, nb_vertices + 1):
            for d in succ[vertex]:
                if prev[d - 1]:
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


def main():
    "Program wrapper."
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+1)
from functools import lru_cache

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

    @lru_cache(maxsize=10**5+1)
    def dp(v):
        res = 0
        for w in G[v]:
            res = max(res, dp(w)+1)
        return res

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dist = [0]*n
for _ in range(n-1):
    for v, v2 in edges:
        if dist[v2] <= dist[v]-1:
            continue
        dist[v2] = dist[v]-1

print(-min(dist))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
graph = defaultdict(list)
for a, b in L:
    graph[a-1].append(b-1)
ans = 0
dist = [0] * N

for i in range(N):
    q = [i]
    while q:
        a = q.pop()
        for node in graph[a]:
            if dist[a] + 1 > dist[node]:
                dist[node] = dist[a] + 1
                # if ans < dist[node]:
                #     ans = dist[node]
                q.append(node)
if ans < max(dist):
    ans = max(dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
graph = defaultdict(list)
for a, b in L:
    graph[a-1].append(b-1)
ans = 0
dist = [0] * N

for i in range(N):
    q = [i]
    while q:
        a = q.pop()
        for node in graph[a]:
            if dist[a] + 1 > dist[node]:
                dist[node] = dist[a] + 1
                if ans < dist[node]:
                    ans = dist[node]
                q.append(node)
    # if ans < max(dist):
    #     ans = max(dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
graph = defaultdict(list)
for a, b in L:
    graph[a-1].append(b-1)
ans = 0
for i in range(N):
    dist = [0] * N
    visited = [False] * N
    q = [i]
    while q:
        a = q.pop()
        for node in graph[a]:
            if dist[a] + 1 > dist[node]:
                dist[node] = dist[a] + 1
                q.append(node)
    if ans < max(dist):
        ans = max(dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
 
from collections import deque
N, M = mi()
x = li2(M)
 
dp = [[0, []] for i1 in range(N+1)]
 
tmp = deque([])
 
for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    tmp.append(x[i][1])
    while tmp != deque():
        a = tmp.popleft()
        if dp[a][1] != []:
            for b in dp[a][1]:
                dp[b][0] = max(dp[a][0] + 1, dp[b][0])
                tmp.append(b)
 
#print(dp)
print(max([row[0] for row in dp]))

Submission status: Time Limit Exceeded

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]

from collections import deque
N, M = mi()
x = li2(M)

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

tmp = deque([])

for i in range(M):
    dp[x[i][1]][0] = max(dp[x[i][1]][0], dp[x[i][0]][0] + 1)
    dp[x[i][0]][1].append(x[i][1])
    tmp.append(x[i][1])
    while tmp != deque():
        a = tmp.popleft()
        if dp[a][1] != []:
            for b in dp[a][1]:
                dp[b][0] = max(dp[a][0] + 1, dp[b][0])
                tmp.append(b)

#print(dp)
print(max([row[0] for row in dp]))