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(10 ** 6)

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

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

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

dp = [None] * (n + 1)
def dfs(now):
    if dp[now] is not None:
        return dp[now]

    if not graph[now]:
        return 0

    r = max(dfs(parent) for parent in graph[now]) + 1
    dp[now] = r
    return r

print(max(dfs(i) for i in range(1, n + 1)))

Submission status: Time Limit Exceeded

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

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

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

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

dp = [None] * (n + 1)
def dfs(now):
    if dp[now] is not None:
        return dp[now]

    if not graph[now]:
        return 0

    return max(dfs(parent) for parent in graph[now]) + 1

print(max(dfs(i) for i in range(1, n + 1)))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
E = []
for _ in range(M):
    u,v = map(int, input().split())
    E.append((u-1,v-1))

dp = [0] * N

changed = True
while changed:
    changed = False
    for u,v in E:
        if dp[u]+1 > dp[v]:
            dp[v] = dp[u]+1
            changed = True

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
INF = float('inf')
N,M = map(int,input().split())

d_from = defaultdict(lambda:[])
d_to = defaultdict(lambda:[])

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

dp = [-INF]*N
for i in range(N):
    if d_from[i] == []:
        dp[i] = 0
        que = deque([])
        for j in d_to[i]:
            dp[j] = max(dp[i]+1,dp[j])
            que.append(j)
        while que:
            j = que.pop()
            for k in d_to[j]:
                dp[k] = max(dp[j]+1,dp[k])
                que.append(k)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

G = [[] for _ in range(N)]
G2 = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1  # 0 startにする
    G[x].append(y)
    G2[y].append(x)

start_node = []
for i, l in enumerate(G2):
    if len(l) == 0:
        start_node.append(i)

# dp[v] := ノードvを始点としたときのパス長の最大値
# BFSでdp[v]を求める
# res = dp[v]として、chmax(res, rec(nv) + 1)

def bfs(start):
    q = [start]
    d = [-1 for _ in range(N)]  # startからiまでの距離がd[i]
    d[start] = 0
    while len(q) > 0:
        u = q.pop()
        for v in G[u]:
            q.append(v)
            d[v] = max(d[v], d[u] + 1)
    return max(d)

max_length = []
for i in start_node:
    max_length.append(bfs(i))

print(max(max_length))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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  # 0 startにする
    G[x].append(y)

# dp[v] := ノードvを始点としたときのパス長の最大値
# BFSでdp[v]を求める
# res = dp[v]として、chmax(res, rec(nv) + 1)

def bfs(start):
    q = [start]
    d = [-1 for _ in range(N)]  # startからiまでの距離がd[i]
    d[start] = 0
    while len(q) > 0:
        u = q.pop()
        for v in G[u]:
            q.append(v)
            d[v] = max(d[v], d[u] + 1)
    return max(d)

max_length = []
for i in range(N):
    max_length.append(bfs(i))

print(max(max_length))

Submission status: Time Limit Exceeded

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

now = [i for i in range(1,N+1) if i not in x]

next = []
kesu = []


while M > 0:
    for i in now:
        if i not in x:
            for j in range(M):
                if y[j] == i:
                    dp[x[j]] = max(dp[x[j]], dp[y[j]] + 1)
                    kesu.append(j)
            
            kesu.sort()
            kesu.reverse()
            for j in kesu:
                next.append(x.pop(j))
                y.pop(j)
                M -= 1

            kesu = []

    now = next
    next = []
    

print(max(dp))

Submission status: Time Limit Exceeded

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


while True:
    for i in tyo:
        if i not in x:
            for j in range(M):
                if y[j] == i:
                    dp[x[j]] = max(dp[x[j]], dp[y[j]] + 1)
                    kesu.append(j)
            
            kesu.sort()
            kesu.reverse()
            for j in kesu:
                x.pop(j)
                y.pop(j)
                M -= 1

            tyo.remove(i)
            kesu = []
            break

    else:
        break

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    es = [(xx-1, yy-1, 0) for xx, yy in zip(x,y)]
    g = DGraph(N, es)

    dp = [-1] * N
    q = deque([(v - 1, 0) for v in set(x).difference(set(y))])
    while 0 < len(q):
        v, c = q.popleft()
        if c <= dp[v]:
            continue
        dp[v] = c
        for _, d, _ in g.edges(v):
            q.append((d, c+1))
    return max([v for v in dp if not isinf(v)])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]" 
    y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, M, x, y)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    es = [(xx-1, yy-1, 0) for xx, yy in zip(x,y)]
    g = DGraph(N, es)

    dp = [-1] * N
    q = deque([(v - 1, 0) for v in set(x).difference(set(y))])
    while 0 < len(q):
        v, c = q.popleft()
        if c <= dp[v]:
            continue
        dp[v] = c
        for _, d, _ in g.edges(v):
            q.append((d, c+1))
    return max([v for v in dp if not isinf(v)])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]" 
    y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, M, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
### 動的計画法のテーブルを用意
# dp(n) は頂点nを始点として時の最大有効パスの長さ

def get_inputs():
    N, M = map(int, input().split())

    # グラフgを初期化
    g = [[] for _ in range(N)]

    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)

    return N, M, g


def getlp(x, depth):
    global dp, g

    if depth >= MAX_DEPTH:
        return -1
    elif dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        mxp = 0
        for y in g[x]:
            yp = getlp(y, depth + 1)
            if yp == -1:
                return -1
            elif yp > mxp:
                mxp = yp
        dp[x] = mxp + 1
        return dp[x]


N, M, g = get_inputs()
MAX_DEPTH = 900

dp = [-1] * N
nodes = list(range(N))
ans = 0

while len(nodes) > 0:
    tmp_nodes = []
    for x in range(N):
        if dp[x] == -1:
            t = getlp(x, 0)
            if t == -1:
                tmp_nodes.append(x)
            else:
                ans = max(ans, t)
        else:
            ans = max(ans, dp[x])

    nodes = list(tmp_nodes)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
### 動的計画法のテーブルを用意
# dp(n) は頂点nを始点として時の最大有効パスの長さ

def get_inputs():
    N, M = map(int, input().split())

    # グラフgを初期化
    g = [[] for _ in range(N)]

    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)

    return N, M, g


def getlp(x, depth):
    global dp, g

    if depth >= MAX_DEPTH:
        return -1
    elif dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        mxp = 0
        for y in g[x]:
            yp = getlp(y, depth + 1)
            if yp == -1:
                return -1
            elif yp > mxp:
                mxp = yp
        dp[x] = mxp + 1
        return dp[x]


N, M, g = get_inputs()
MAX_DEPTH = 800

dp = [-1] * N
nodes = list(range(N))
ans = 0

while len(nodes) > 0:
    tmp_nodes = []
    for x in range(N):
        if dp[x] == -1:
            t = getlp(x, 0)
            if t == -1:
                tmp_nodes.append(x)
            else:
                ans = max(ans, t)
        else:
            ans = max(ans, dp[x])

    nodes = list(tmp_nodes)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
### 動的計画法のテーブルを用意
# dp(n) は頂点nを始点として時の最大有効パスの長さ

def get_inputs():
    N, M = map(int, input().split())

    # グラフgを初期化
    g = [[] for _ in range(N)]

    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)

    return N, M, g


def getlp(x, depth):
    global dp, g

    if depth >= MAX_DEPTH:
        return -1
    elif dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        mxp = 0
        for y in g[x]:
            yp = getlp(y, depth + 1)
            if yp == -1:
                return -1
            elif yp > mxp:
                mxp = yp
        dp[x] = mxp + 1
        return dp[x]


N, M, g = get_inputs()
MAX_DEPTH = 500

dp = [-1] * N
nodes = list(range(N))
ans = 0

while len(nodes) > 0:
    tmp_nodes = []
    for x in range(N):
        if dp[x] == -1:
            t = getlp(x, 0)
            if t == -1:
                tmp_nodes.append(x)
            else:
                ans = max(ans, t)
        else:
            ans = max(ans, dp[x])

    nodes = list(tmp_nodes)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

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

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

#memo = [-1]*n

@lru_cache(maxsize=None)
def longest(v): #nを終点とするlongest
#    if memo[v] >= 0:
#        return memo[v]
#    else:
    c=0
    for j in oya[v]:
        c = max(c,longest(j)+1)
#    memo[v] = c
    return c

memo = [longest(i) for i in range(n)]

print(max(memo))    
#print(memo)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

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

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

#memo = [-1]*n

@lru_cache()
def longest(v): #nを終点とするlongest
#    if memo[v] >= 0:
#        return memo[v]
#    else:
    c=0
    for j in oya[v]:
        c = max(c,longest(j)+1)
#    memo[v] = c
    return c

memo = [longest(i) for i in range(n)]

print(max(memo))    
#print(memo)

Submission status: Time Limit Exceeded

Solution code:
def g():
    N, M = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(M)]
    memo = {}

    def g2(x):
        if x in memo:
            return memo[x]
        else:
            r = 0
            for xx, yy in xy:
                if x == xx:
                    r = max(r, g2(yy) + 1)
            memo[x] = r
        return r

    ans = [g2(i) for i in range(1, N + 1)]
    return max(ans)


if __name__ == '__main__':
    ans = g()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, e = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
source_num = [0] * n
distance = [0] * n
for i in range(e):
    f, t = map(int, input().split())
    f -= 1
    t -= 1
    source_num[t] += 1
    edge[f].append(t)
while e > 0:
    for i, item in enumerate(source_num):
        if item != 0:
            continue
        source_num[i] = -1
        for v in edge[i]:
            distance[v] = max(distance[v], distance[i] + 1)
            source_num[v] -= 1
            e -= 1
print(max(distance))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
 
def sub():
    import sys
    sys.setrecursionlimit(10000)

    N, M = [int(e) for e in input().split()]
    
    class ListDict(dict):
        def __missing__(self, key):
            self[key] = []
            return self[key]
 
    d_edge = ListDict()
    for _ in range(M):
        h, t = [int(e) for e in input().split()]
        d_edge[h].append(t)
 
    # for k, v in d_edge.items():
    #     print(k,v)
    
    @lru_cache(maxsize=None)
    def dp(a_head):
        tails = d_edge[a_head]
        if len(tails) == 0:
            return 0
        tmps = [dp(t) for t in tails]
        return max(tmps) + 1
    
    heads = list(d_edge.keys())
    rr = [dp(h) for h in heads]
    print(max(rr))
 
 
if __name__ == "__main__":
    sub()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = list(map(int, input().split()))
G = np.zeros(0, dtype=int)

for i in range(M):
    G = np.append(G, list(map(int, input().split())))
G = G.reshape(M, 2)
V = [0]*N

for i, g in enumerate(G):
    V[g[1]-1] = max(V[g[1]-1], V[g[0]-1]+1) 

print(np.max(V))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
childs = [[] for _ in range(N)]
for i in range(M):
    p, c = map(int, input().split())
    childs[p-1].append(c)

stack = list(range(1, N+1))
# dp[n]: nに到達する最長のパス
dp = [0] * N
while stack:
    n = stack.pop()
    for nc in childs[n-1]:
        if dp[nc-1] < dp[n-1] + 1:
            stack.append(nc)
            dp[nc-1] = dp[n-1] + 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
edges = [[0, 0] for _ in range(M)]
for i in range(M):
    edges[i][0], edges[i][1] = map(int, input().split())

stack = list(range(1, N+1))
# dp[n]: nに到達する最長のパス
dp = [0] * N
while stack:
    n = stack.pop()
    childs = [edge[1] for edge in edges if edge[0] == n]
    for nc in childs:
        if dp[nc-1] < dp[n-1] + 1:
            stack.append(nc)
            dp[nc-1] = dp[n-1] + 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
edges = [[0, 0] for _ in range(M)]
for i in range(M):
    edges[i][0], edges[i][1] = map(int, input().split())

stack = list(range(1, N+1))
# dp[n]: nに到達する最長のパス
dp = [0] * N
while stack:
    n = stack.pop()
    childs = [edge[1] for edge in edges if edge[0] == n]
    for nc in childs:
        stack.append(nc)
        if dp[nc-1] < dp[n-1] + 1:
            dp[nc-1] = dp[n-1] + 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
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
for i in range(n - 1):
    for j in range(n):
        if graph[j] is not None:
            for k in graph[j]:
                dp[j] = max(dp[j], dp[k] + 1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.insert(0, i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    xv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for x, v in xv:
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = []

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = tsort_res[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

# 再帰的に更新
def update_dp(dp, n):
    for i in nextl[n]:
        if dp[i] < dp[n] + 1:
            dp[i] = dp[n]+1
            update_dp(dp, i)


if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    xv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

    # iにいくまでの最長のパス
    dp = [0] * (N+1)

    # iのnextを保持するリスト
    nextl = [[] for _ in range(N+1)]

    for x, v in xv:
        if dp[v] < dp[x] + 1:
            dp[v] = dp[x]+1
            update_dp(dp, v)
        nextl[x].append(v)

    # for DEBUG
    #print(dp)
    print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

# 再帰的に更新
def update_dp(dp, n):
    for i in nextl[n]:
        dp[i] = max(dp[i], dp[n]+1)
        update_dp(dp, i)


if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    xv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

    # iにいくまでの最長のパス
    dp = [0] * (N+1)

    # iのnextを保持するリスト
    nextl = [[] for _ in range(N+1)]

    for x, v in xv:
        dp[v] = max(dp[v], dp[x]+1)
        update_dp(dp, v)
        nextl[x].append(v)

    # for DEBUG
    #print(dp)
    print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

x_to_y = defaultdict(list)
y_to_x = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)
    y_to_x[y].append(x)

# 終端をサーチ
ends = [x for x in range(1, N  +1) if x not in x_to_y.keys()]
starts = [y for y in range(1, N + 1) if y not in y_to_x.keys()]

def search_next(current):
    # まだ探索していない前のノードがあればそちらを優先する
    for y in x_to_y[current]:
        if dp[y] == -1:
            continue

    for next_node in y_to_x[current]:
        dp[next_node] = max(dp[next_node], dp[current] + 1)
        search_next(next_node)


        

for end in ends:
    dp[end] = 0
    search_next(end)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
h={}
st=set([i for i in range(1,n+1)])
kos=set()
for _ in range(m):
    oy,ko=map(int,input().split())
    h.setdefault(oy,[])
    h[oy]+=[ko]
    kos.add(ko)
st=st-kos
dep=0
while 1:
    nst=set()
    for s in st:
        if s not in h:continue
        for ko in h[s]:
            nst.add(ko)
    if len(nst)==0:
        break
    st=nst
    dep+=1
print(dep)

Submission status: Time Limit Exceeded

Solution code:
#!/snap/bin/pypy3
import sys

MEMO = dict()

def search(n, data):
    global MEMO

    if n in MEMO:
        return MEMO[n]
    else:
        if not n in data:
            MEMO[n] = 0
            return 0

        MEMO[n] = max(search(i, data) for i in data[n]) + 1
        return MEMO[n]


def main():
    sys.setrecursionlimit(65535)
    N, M = map(int, input().split())
    data = dict()
    for _ in range(M):
        x, y = map(int, input().split())
        if x not in data:
            data[x] = [y]
        else:
            data[x].append(y)

    print(max(search(n, data) for n in range(1, N+1)))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    else:
        return b

def main():  
    # 入力
    N, M = map(int, input().split())
    # 隣接関係は隣接リストで管理する
    lst_edge = [[] for _ in range(N)]
    # 各頂点の入力辺の本数
    deg = [0] * N  
    for _ in range(M):
        x, y = map(int, input().split())
        # 最初のindexをゼロにする
        lst_edge[x-1].append(y-1)
        deg[y-1] += 1
    
    # 入力辺を持たない頂点をqueueに入れる
    que = collections.deque()
    for v in range(N):
        if deg[v] == 0:
            que.append(v)

    # 各頂点の最初に入力辺を持たなかった点からの距離
    dp = [0] * N  

    while list(que) != []:
        v = que.popleft()
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            # エッジ(v, nv)をグラフから削除する
            deg[nv] -= 1
            if deg[nv] == 0:
                # エッジがなくなったことで、入力辺がなくなったらqueueに入れる
                que.append(nv)
                # 最初に入力辺を持たなかった点からの距離
                dp[nv] = chmax(dp[nv], dp[v] + 1)
    
    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
    
def g(to_li, from_li, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n == 0:
        return 0
    val = max([g(to_li, from_li, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    

def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N+2)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N+2)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x].append(y)
        to_li[y].append(x)
    parents = []
    children = []
    dp = [-1]*(N+2)
    for index, to in enumerate(to_li):
        if len(to) == 0 and index != N+1 and index != 0:
            from_li[0].append(index)
            to_li[index].append(0)
    for index, fr in enumerate(from_li):
        if len(fr) == 0 and index != 0 and index != N+1:
            to_li[N+1].append(index)
            from_li[index].append(N+1)
    
    print(g(to_li, from_li, dp, N+1) - 2)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    
def g(to_li, from_li, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n == 0:
        return 0
    val = max([g(to_li, from_li, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    

def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N+2)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N+2)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x].append(y)
        to_li[y].append(x)
    parents = []
    children = []
    dp = [-1]*(N+2)
    for index, to in enumerate(to_li):
        if len(to) == 0 and index != N+1 and index != 0:
            from_li[0].append(index)
            to_li[index].append(0)
    for index, fr in enumerate(from_li):
        if len(fr) == 0 and index != 0 and index != N+1:
            to_li[N+1].append(index)
            from_li[index].append(N+1)
    
    print(g(to_li, from_li, dp, N+1) - 2)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    
def g(to_li, from_li, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n == 0:
        return 0
    val = max([g(to_li, from_li, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    

def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N+2)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N+2)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x].append(y)
        to_li[y].append(x)
    parents = []
    children = []
    dp = [-1]*(N+2)
    for index, to in enumerate(to_li):
        if index != N+1 and index != 0 and len(to) == 0:
            from_li[0].append(index)
            to_li[index].append(0)
    for index, fr in enumerate(from_li):
        if index != 0 and index != N+1 and len(fr) == 0:
            to_li[N+1].append(index)
            from_li[index].append(N+1)
    
    print(g(to_li, from_li, dp, N+1) - 2)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x-1].append(y-1)
        to_li[y-1].append(x-1)
    parents = []
    children = []
    dp = [-1]*N
    for index, to in enumerate(to_li):
        if len(to) == 0:
            parents.append(index)
    for index, fr in enumerate(from_li):
        if(len(fr)) == 0:
            children.append(index)
    print(max([g(to_li, from_li, parents, dp, c) for c in children]))

    
def g(to_li, from_li, parents, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n in parents:
        return 0
    val = max([g(to_li, from_li, parents, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

# dp[i] = 頂点iまでの最長経路
dp = [0 for i in range(N+1)]

stack=[]
for i in range(1,N+1):
    if len(road_to[i]) == 0:
        stack.append(i)
try:
    while True:
        i = stack.pop()
        for j in road_from[i]:
            if dp[j] < dp[i]+1:
                dp[j] = dp[i]+1
                stack.append(j)

except IndexError:
    pass

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

# dp[i] = 頂点iまでの最長経路
dp = [0 for i in range(N+1)]
updated=True
while updated:
    updated=False
    for i in range(1,N+1):
        for j in road[i]:
            if dp[j] < dp[i]+1:
                dp[j] = dp[i]+1
                updated=True
print(max(dp))