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 unittest


class TestG(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(
                4,
                [
                  [1, 2], [1, 3], [3, 2],
                  [2, 4], [3, 4]
                ]
            ),
            3
        )

    def test_2(self):
        self.assertEqual(
            think(
                6,
                [
                    [2, 3], [4, 5], [5, 6]
                ]
            ),
            2
        )

    def test_3(self):
        self.assertEqual(
            think(
                5,
                [
                    [5, 3], [2, 3], [2, 4], [5, 2],
                    [5, 1], [1, 4], [4, 3], [1, 3]
                ]
            ),
            3
        )


def solve():
    n, list_of_x_and_y = read()
    result = think(n, list_of_x_and_y)
    write(result)


def read():
    n, m = read_int(2)
    list_of_x_and_y = []
    for _ in range(m):
        list_of_x_and_y.append(read_int(2))
    return n, list_of_x_and_y


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, list_of_x_and_y):
    inf = n ** 2
    adjacency_matrix = create_adjacency_matrix(n, list_of_x_and_y)
    max_distance = 0
    for i in range(n):
        max_distance = max(max_distance, scan_max_distance_from(n, i, [], adjacency_matrix))
    return max_distance


def write(result):
    print(result)


def create_adjacency_matrix(n, list_of_x_and_y):
    matrix = prepare_empty_matrix(n, 0)
    for x, y in list_of_x_and_y:
        matrix[x - 1][y - 1] = 1
    return matrix


def prepare_empty_matrix(n, initial_value):
    return [[initial_value for y in range(n)] for x in range(n)]


def scan_max_distance_from(n, at, path, adjacency_matrix):
    max_distance = len(path)
    for i in range(n):
        if i in path:
            continue
        if adjacency_matrix[at][i] == 0:
            continue
        path.append(i)
        max_distance = max(
            max_distance,
            scan_max_distance_from(n, i, path, adjacency_matrix)
        )
        path.remove(i)
    return max_distance


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(100000)
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

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

graph = [[] for i in range(N)]
is_root = [True] * N
for i in range(M):
  x, y = map(int, input().split())
  graph[x-1].append(y-1)
  is_root[y-1] = False


depth = [0] * N
d = [i for i in range(N) if is_root[i]]
while d:
  node = d.pop()
  children = graph[node]
  _depth = depth[node] + 1
  for child in children:
    if depth[child] < _depth:
      depth[child] = _depth
      d.append(child)

print(max(depth))

Submission status: Time Limit Exceeded

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

graph = [[] for i in range(N)]
is_root = [True] * N
for i in range(M):
  x, y = map(int, input().split())
  graph[x-1].append(y-1)
  is_root[y-1] = False


depth = [0] * N
d = [i for i in range(N) if is_root[i]]
while d:
  node = d.pop()
  children = graph[node]
  _depth = depth[node] + 1
  for child in children:
    if depth[child] < _depth:
      depth[child] = _depth
      d.append(child)

print(max(depth))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(M)]
  
hashi = [1] * (N + 1)
for X, Y in XY:
  hashi[Y] = 0

dist = [-1] * (N + 1) # 最大:-1、最小:INF

graph = [[] for _ in range(N + 1)]
for X, Y in XY:
  graph[X].append(Y)
#print("graph:", graph)

def bfs(x):
  from collections import deque
  
  stack = deque([x])
  dist[x] = 0
  while stack:
    i = stack.popleft()
    for j in graph[i]:
      dist_i = dist[i]
      if dist_i + 1 > dist[j]:
        dist[j] = dist_i + 1
        stack.append(j)
  #print(*dist) 
  
  #return dist

for i in range(1, N + 1):
  if hashi[i]:
    bfs(i)
    
print(max(dist[1::]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

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

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

for i in range(n):
    if indeg[i] == 0:
        q.append(i)
        dp[i] = 0

while q:
    v = q.popleft()
    for w in g[v]:
        if dp[w] < dp[v]+1:
            dp[w] = dp[v]+1
            q.append(w)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

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

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

for i in range(n):
    if indeg[i] == 0:
        q.append(i)
        dp[i] = 0

while q:
    v = q.pop()
    for w in g[v]:
        dp[w] = max(dp[w], dp[v]+1)
        q.append(w)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
nodeFrom = [0] * n
ans = [0] * n

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

for i, f in enumerate(nodeFrom):
    if not f == 0:
        continue
    start = [i]
    while start:
        s = start.pop()
        start.extend(nodeToGo[s])
        for node in nodeToGo[s]:
            ans[node] = max(ans[node], ans[s]+1)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
y_list = [0] * n
start = []
ans = [0] * n
for _ in range(m):
    x, y = map(int, input().split())
    y_list[y-1] += 1
    nodeToGo[x-1].append(y-1)

for j, yn in enumerate(y_list):
    if yn == 0:
        start.append(j)
    
while start:
    s = start.pop()
    start.extend(nodeToGo[s])
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
y_list = [0] * n
start = []
ans = [0] * n
for _ in range(m):
    x, y = map(int, input().split())
    y_list[y-1] += 1
    nodeToGo[x-1].append(y-1)

for j, yn in enumerate(y_list):
    if yn == 0:
        start.append(j)
    
while start:
    s = start.pop()
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
y_list = [0] * n
start = []
ans = [0] * n
for _ in range(m):
    x, y = map(int, input().split())
    y_list[y-1] += 1
    nodeToGo[x-1].append(y-1)

for j, yn in enumerate(y_list):
    if yn == 0:
        start.append(j)
    
while not len(start) == 0:
    s = start.pop()
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
y_list = [0] * n
start = []
ans = [0] * n
for _ in range(m):
    x, y = map(int, input().split())
    y_list[y-1] += 1
    nodeToGo[x-1].append(y-1)

for j, yn in enumerate(y_list):
    if yn == 0:
        start.append(j)
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
y_list = [0] * n
start = []
ans = [0] * n
for _ in range(m):
    x, y = map(int, input().split())
    y_list[y-1] += 1
    if not y-1 in nodeToGo[x-1]:
        nodeToGo[x-1].append(y-1)

for j, yn in enumerate(y_list):
    if yn == 0:
        start.append(j)
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
y_list = [0] * n
start = []
ans = [0] * n
for i in range(m):
    x, y = map(int, input().split())
    y_list[y-1] += 1
    if not y-1 in nodeToGo[x-1]:
        nodeToGo[x-1].append(y-1)

for j, yn in enumerate(y_list):
    if yn == 0:
        start.append(j)
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)
    start = list(set(start))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
start = []
ans = [0] * n
for i in range(m):
    x, y = map(int, input().split())
    ans[y-1] += 1
    if not y-1 in nodeToGo[x-1]:
        nodeToGo[x-1].append(y-1)

for j, a in enumerate(ans):
    if a == 0:
        start.append(j)
    ans[j] = 0
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)
    start = list(set(start))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
y_list = [0] * n
start = []
ans = [0] * n
for i in range(m):
    x, y = map(int, input().split())
    y_list[y-1] += 1
    if not y-1 in nodeToGo[x-1]:
        nodeToGo[x-1].append(y-1)

for j, yn in enumerate(y_list):
    if yn == 0:
        start.append(j)
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
start = [s for s in range(n)]
ans = [0] * n
for i in range(m):
    x, y = map(int, input().split())
    if y-1 in start:
        start.remove(y-1)
    if not y-1 in nodeToGo[x-1]:
        nodeToGo[x-1].append(y-1)
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
start = [s for s in range(n)]
ans = [0] * n
for i in range(m):
    x, y = map(int, input().split())
    if y-1 in start:
        start.remove(y-1)
    if not y-1 in nodeToGo[x-1]:
        nodeToGo[x-1].append(y-1)
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)
    start = list(set(start))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
start = [s for s in range(n)]
ans = [0] * n
for i in range(m):
    x, y = map(int, input().split())
    if y-1 in start:
        start.remove(y-1)
    if not y-1 in nodeToGo[x-1]:
        nodeToGo[x-1].append(y-1)
    
while not len(start) == 0:
    s = start.pop()
    if len(nodeToGo[s]) == 0:
        continue
    for node in nodeToGo[s]:
        ans[node] = max(ans[node], ans[s]+1)
        start.append(node)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

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

check = True
while(check):
    check = False
    for i in range(m):
        x, y  =xy[i]
        if(dp[x][1] < dp[y][1]+1):
            dp[x][1] =  dp[y][1]+1
            check = True
        if(dp[y][0] < dp[x][0]+1):
            dp[y][0] = dp[x][0]+1
            check = True

ans = 0
for i in range(n+1):
     ans = max(ans, dp[i][0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

tree = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)

set_ = set([])
for i in range(n):
    for j in tree[i]:
        set_.add(j)

start = set([])
for i in range(n):
    if i not in set_:
        start.add(i)

q = deque([])
for i in start:
    q.append(i)
dp = [0]*n
while q:
    pos = q.popleft()
    for next_pos in tree[pos]:
        if dp[pos] + 1 > dp[next_pos]:
            dp[next_pos] = dp[pos] + 1
            q.append(next_pos)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

tree = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)

set_ = set([])
for i in range(n):
    for j in tree[i]:
        set_.add(j)

start = set([])
for i in range(n):
    if i not in set_:
        start.add(i)

q = []
for i in start:
    heapq.heappush(q, (0, i))
dp = [0]*n
while q:
    cnt, pos = heapq.heappop(q)
    cnt = -cnt
    for next_pos in tree[pos]:
        if cnt + 1 > dp[next_pos]:
            dp[next_pos] = cnt + 1
            heapq.heappush(q, (-(cnt + 1), next_pos))
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

tree = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)

set_ = set([])
for i in range(n):
    for j in tree[i]:
        set_.add(j)

start = set([])
for i in range(n):
    if i not in set_:
        start.add(i)

q = []
for i in start:
    heapq.heappush(q, (0, i))
dp = [0]*n
while q:
    cnt, pos = heapq.heappop(q)
    for next_pos in tree[pos]:
        if cnt + 1 > dp[next_pos]:
            dp[next_pos] = cnt + 1
            heapq.heappush(q, (cnt + 1, next_pos))
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
XY = []
for i in range(M):
    xy = list(map(int,input().split()))
    XY.append(xy)
p = [i+1 for i in range(N)]
ans = []
stack = []
alr = []
xy1 = []
for xy in XY:
    xy1.append(xy[1])
for i in range(1,N+1):
    if i not in xy1:
        stack.append(i)
        alr.append(i)

while len(stack) > 0:
    p1 = stack.pop(-1)
    flag = True
    for xy in XY:
        if p1 == xy[0]:
            alr.append(xy[1])
            stack.append(xy[1])
        if (p1 == xy[1]) and (xy[0] not in ans):
            flag = False
    if flag:
        ans.append(p1)

    
dp = [0 for i in range(len(ans))]

for i in range(len(ans)):
    for j in range(i):
        if [ans[j],ans[i]] in XY:
            dp[i] = max(dp[i],dp[j]+1)


print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
XY = []
for i in range(M):
    xy = list(map(int,input().split()))
    XY.append(xy)
p = [i+1 for i in range(N)]
ans = []

while len(p) >= 1:
    for i in p:
        flag = True
        for xy in XY:
            if i == xy[1] and xy[0] not in ans:
                flag = False
        if flag:
            ans.append(i)
            p.remove(i)

dp = [0 for i in range(len(ans))]

for i in range(len(ans)):
    for j in range(i):
        if [ans[j],ans[i]] in XY:
            dp[i] = max(dp[i],dp[j]+1)


print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
path = [[] for _ in range(n)]
ans = 0

for i in range(m):
    x, y = map(int, input().split())
    if not y-1 in path[x-1]:
        path[x-1].append(y-1)
    
def get_next_node(current):
    next_node = []
    for c in current:
        next_node += path[c]
    return list(set(next_node))
    
for j in range(n):
    count = 0
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans = max(ans, count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
path = [[] for _ in range(n)]
ans = 0

for i in range(m):
    x, y = map(int, input().split())
    path[x-1].append(y-1)
    
def get_next_node(current):
    next_node = []
    for c in current:
        next_node += path[c]
    return list(set(next_node))
    
for j in range(n):
    count = 0
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans = max(ans, count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
path = {}
ans = 0

for i in range(m):
    x, y = map(int, input().split())
    if not x in path.keys():
        path[x] = []
    path[x].append(y)
    
def get_next_node(current):
    next_node = []
    for c in current:
        if not c in path.keys():
            continue
        next_node += path[c]
    return list(set(next_node))
    
for j in range(1, n+1):    
    if not j in path.keys():
        continue
    if len(path[j]) == 0:
        continue
    count = 0
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans = max(ans, count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
path = {}
ans = 0

for i in range(m):
    x, y = map(int, input().split())
    if not x in path.keys():
        path[x] = []
    path[x].append(y)
    
def get_next_node(current):
    next_node = []
    for c in current:
        if not c in path.keys():
            continue
        next_node += path[c]
    return list(set(next_node))
    
for j in range(1, n+1):    
    if not j in path.keys():
        continue
    count = 0
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans = max(ans, count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
path = {}
ans = []

for i in range(m):
    x, y = map(int, input().split())
    if not x in path.keys():
        path[x] = []
    path[x].append(y)
    
def get_next_node(current):
    next_node = []
    for c in current:
        if not c in path.keys():
            continue
        next_node += path[c]
    return list(set(next_node))
    
for j in range(1, n+1):
    count = 0
    if not j in path.keys():
        continue
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans.append(count)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
path = {}
ans = []

for i in range(m):
    x, y = map(int, input().split())
    if not x in path.keys():
        path[x] = []
    path[x].append(y)
    
def get_next_node(current):
    next_node = []
    for c in current:
        if not c in path.keys():
            continue
        next_node += path[c]
    return next_node
    
for j in range(1, n+1):
    count = 0
    if not j in path.keys():
        continue
    next_node = path[j]
    while len(next_node) != 0:
        next_node = get_next_node(next_node)
        count += 1
    ans.append(count)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    import collections
    dic=collections.defaultdict(list)

    N,M=list(map(int,sys.stdin.readline().split()))
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x].append(y)


    dp=[0]*(N+1)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if frm not in dic.keys():
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)

        dp[frm]=mx
        return mx

    mx=0
    for key in dic.keys():
        mx=max(mx,dfs(key))

    return mx

print(main())

Submission status: Time Limit Exceeded

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

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(N)]
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x-1].append(y-1)


    dp=[0]*(N)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if not dic[frm]:
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)
        return mx

    mx=0
    for key in range(N):
        mx=max(mx,dfs(key))

    return mx

print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    import collections
    dic=collections.defaultdict(list)

    N,M=list(map(int,sys.stdin.readline().split()))
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x].append(y)


    dp=[0]*(N+1)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if frm not in dic.keys():
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)
        return mx

    mx=0
    for key in dic.keys():
        mx=max(mx,dfs(key))

    return mx

print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
root_cand = set(list(range(1, n+1))) - not_root
root_cand = deque(root_cand)
dp = [0] * (n+1)
def dfs(node, count):
    dp[node] = count + 1
    if len(adjacent_list[node]) != 0:
        for i in adjacent_list[node]:
            if dp[i] <= dp[node]:
                dfs(i, dp[node])
n = len(root_cand)
while n != 0:
    root = root_cand.pop()
    n -= 1
    dfs(root, -1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
root_cand = set(list(range(1, n+1))) - not_root
root_cand = deque(root_cand)
dp = [0] * (n+1)
def dfs(node, count):
    dp[node] = max(dp[node], count + 1)
    if len(adjacent_list[node]) != 0:
        for i in adjacent_list[node]:
            if dp[i] <= dp[node]:
                dfs(i, dp[node])
while len(root_cand) != 0:
    root = root_cand.pop()
    dfs(root, -1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys 
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
root_cand = set(list(range(1, n+1))) - not_root
root_cand = deque(root_cand)
dp = [0] * (n+1)
def dfs(node, count):
    dp[node] = max(dp[node], count + 1)
    if len(adjacent_list[node]) != 0:
        for i in adjacent_list[node]:
            if dp[i] <= dp[node]:
                dfs(i, dp[node])
while len(root_cand) != 0:
    root = root_cand.pop()
    dfs(root, -1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys 
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
root_cand = set(list(range(1, n+1))) - not_root
root_cand = deque(root_cand)
dp = [0] * (n+1)
def dfs(node, count):
    dp[node] = max(dp[node], count + 1)
    if len(adjacent_list[node]) != 0:
        for i in adjacent_list[node]:
            dfs(i, dp[node])

while len(root_cand) != 0:
    root = root_cand.pop()
    dfs(root, -1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
def dfs(num,count,ans):
    #print(num,count)
    ans=max(ans,count)
    for index,item in enumerate(l[num-1]):
        if item==1:
            dp[index+1]=max(dp[index+1],count)
            ans=dfs(index+1,count+1,ans)
    return ans
    
N,M=map(int,input().split())

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

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

for _ in range(M):
    x,y=map(int,input().split())
    l[x-1][y-1]=1
    try:
        start.remove(y)
    except:
        pass
#print(l)

dp=[0]*(N+1)
ans=0
for i in start:
    ans=max(dfs(i,0,0),ans)

#print(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calcpath(n):
    if DP[n] != -1:
        return DP[n]
    if not n in Data.keys():
        DP[n] = 0
        return DP[n]
    else:
        max1 = 0
        for e in Data[n]:
            max1 = max(max1,calcpath(e)+1)
        DP[n] = max1
        return DP[n]

N,M = map(int,input().split())
Data = {}
for _ in range(M):
    x,y = map(int,input().split())
    if x in Data.keys():
        Data[x].append(y)
    else:
        Data[x] = [y]
DP = [-1]*(N+1)

for n in range(1,N+1):
    if n != -1:
        calcpath(n)

ans = max(DP)
print( ans )

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
sys.setrecursionlimit(10 ** 6)
d = collections.defaultdict(list)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

while(cur):
  nxt = set()
  for x in cur:
    for y in path[x]:
      dp[y] = max(dp[y],dp[x]+1)
      nxt.add(y)
  cur = []
  for x in nxt:
    cur.append(x)
print(max(dp))

Submission status: Time Limit Exceeded

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

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


def dfs(n):
    if dp[n] > 0:
        return dp[n]

    ma = 0
    for b in G[n]:
        ma = max(ma, dfs(b) + 1)
    return ma


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


N, M = map(int, input().split())
A = []
for _ in range(M):
    a = tuple(map(int, input().split()))
    A.append(a)
dp = [-1]*(N+1)


def dfs(n):
    global dp
    B = list(filter(lambda x: x[0] == n, A))
    if len(B) == 0:
        return 0
    ma = 0
    for b in B:
        x = dp[b[1]]
        if x != -1:
            ma = max(ma, x + 1)
        else:
            ma = max(ma, dfs(b[1]) + 1)
    dp[n] = ma
    return ma


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i+1)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
from collections import defaultdict
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))

T = defaultdict(list)

Y = [True] * N
for _ in range(M):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    T[x].append(y)
    Y[y] = False

DP = [0] * N

q = deque()
for n in range(N):
    if Y[n]:
        q.append(n)


while q:
    e = q.popleft()
    for t in T[e]:
        DP[t] = max(DP[e] + 1, DP[t])
        q.append(t)

print(max(DP))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)

N,M=map(int,input().split())
xy = [list(map(int, input().split())) for _ in range(M)]
to = [[]*(N+1) for _ in range(N+1)]
for i in range(M):
    x,y=xy[i]
    to[x].append(y)

dp = [0]*(N+1)

def saiki(v):
    for u in to[v]:
        if dp[u] < dp[v]+1:
            dp[u]=dp[v]+1
            saiki(u)

count = [True]*(N+1)
count[0] = False
for i in range(M):
    count[xy[i][1]] = False

for i in range(1,N+1):
    if count[i]:
        saiki(i)
print(max(dp))

Submission status: Time Limit Exceeded

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

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

dp = [0]*(N+1)
Flag=True
while Flag:
    Flag=False
    for i in range(M):
        if dp[xy[i][1]] < dp[xy[i][0]]+1:
            dp[xy[i][1]] = dp[xy[i][0]]+1
            Flag=True
print(max(dp))