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: Runtime Error

Solution code:
import networkx as nx
def main():
    G=setup_graph()
    print_longest_path(G)
def setup_graph():
    G=nx.DiGraph()
    G.add_edges_from(tuple(tuple(list(map(int,input().split())))for _ in range(int(input().split()[1]))))
    return G
def print_longest_path(G):
    print(len(nx.dag_longest_path(G))-1)
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def rec(vv):
    res = 0
    for nv in g[vv]:
        if p[nv] >= 0:
            res = max(res, p[nv] + 1)
        else:
            res = max(res, rec(nv) + 1)
    p[vv] = res
    return res


N, M = map(int, input().split())
g = [[] for _ in range(N)]
p = [-1 for _ in range(N)]

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

ans = 0
for v in range(N):
    ans = max(ans, rec(v))
print(ans)

Submission status: Runtime Error

Solution code:
def g_longest_path(N, M, Edges):
    """
    N頂点M辺の有向グラフGが与えられる。Gは有向閉路を含まない。
    Gの有向パスのうち、最長のものについてその長さを求めよ。
    有向パスの長さとは、有向パスに含まれる辺の本数のことをいう。
    """
    # 隣接リストでグラフを持つ(0-based)
    graph = [[] for _ in range(N)]
    for x, y in Edges:
        graph[x - 1].append(y - 1)

    # メモ化再帰
    # ある頂点vから辿っていけるパスの長さは、vに着くまでにどのようにパスを
    # 辿ってきたかと無関係(有向閉路がないため)なので、この方法が使える
    def memorized_recursive(v):
        if dp[v] != -1:
            return dp[v]  # 頂点vはすでに更新済み

        ret = 0
        # 頂点vから1つ辺を通って行ける頂点の集合に対して同じ計算を行う
        for nv in graph[v]:
            ret = max(ret, memorized_recursive(nv) + 1)
        dp[v] = ret  # メモに追加
        return ret

    ans = 0
    dp = [-1] * N  # dp[v]: ノードvを始点としたときの、Gの有効パスの長さの最大値
    # 各頂点に対して調べる
    for v in range(N):
        ans = max(ans, memorized_recursive(v))
    return ans

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(g_longest_path(N, M, Edges))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
info = [[] for _ in range(N+1)] # i -> info[i] 行き先
for _ in range(M):
    x,y = map(int,input().split())
    info[x].append(y)

len_list = []
visited_list = []
def visited(p):
    for e in visited_list:
        if e == p:
            return True
    return False
def dfs(p, length = 0):
    # 訪問済みならlength-1をメモ
    if visited(p) is True:
        len_list.append(length-1)
    # 訪問の印を付ける
    visited_list.append(p)
    # 行き場所がなければlengthをメモ
    if info[p] == []:
        len_list.append(length)
    for d in info[p]:
        dfs(d, length + 1)
for i in range(1,N+1):
    dfs(i)
    visited_list.clear()
ans = max(len_list)
print(ans)

Submission status: Runtime Error

Solution code:
import collections
n, m = [int(i) for i in input().split()]
todc = collections.defaultdict(lambda: [])
lendc = collections.defaultdict(lambda: -1)

for k in range(m):
    i, j = input().split()
    todc[int(j)] += [int(i)]

def maxlen(n):
    if len(todc[n]) == 0:
        lendc[n] = 0
        return 0
    else:
        m = 0
        for i in todc[n]:
            if lendc[i] == -1:
                lendc[i] = maxlen(i)
            m = max(m, lendc[i]+1)
        return m

k = 0
for i in range(1, n+1):
    if lendc[i] == -1:
        lendc[i] = maxlen(i)
    k = max(k, lendc[i])
print(k)

Submission status: Runtime Error

Solution code:
import collections
n, m = [int(i) for i in input().split()]
todc = collections.defaultdict(lambda: [])

for k in range(m):
    i, j = input().split()
    todc[int(j)] += [int(i)]

def maxlen(n):
    if len(todc[n]) == 0:
        return 0
    else:
        m = 0
        for i in todc[n]:
            m = max(m, (maxlen(i)+1))
        return m

k = 0
for i in range(1, n+1):
    k = max(k, maxlen(i))
print(k)

Submission status: Runtime Error

Solution code:
import collections
n, m = [int(i) for i in input().split()]
todc = collections.defaultdict(lambda: [])

for k in range(m):
    i, j = input().split()
    todc[int(j)] += [int(i)]

def maxlen(n):
    if len(todc[n]) == 0:
        return 0
    else:
        m = 0
        for i in todc[n]:
            m = max(m, (maxlen(i)+1))
        return m

k = 0
for i in range(1, n+1):
    k = max(k, maxlen(i))
    print("k ", i, maxlen(i))
print(k)

Submission status: Runtime Error

Solution code:
import collections, sys

n, m = map(int, input().split())
nxts = collections.defaultdict(list)
for line in sys.stdin:
    x, y = map(int, line.split())
    nxts[x].append(y)

memo = {}

def solve(x):
    if not x in memo:
        ans = 0
        for nxt in nxts[x]:
            ans = max(ans, solve(nxt) + 1)
        memo[x] = ans
    return memo[x]

print(max(solve(x) for x in range(1, n + 1)))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
d={}
dp={}

for _ in range(m):
	x,y=map(int,input().split())
	try:
		d[x].append(y)
	except:
		d[x]=[y]

def lp(a):
	if a in dp:
		return dp[a]
	if a not in d:
		dp[a]=1
		return 1
	ans=0
	for i in d[a]:
		ans=max(ans,1+lp(i))
	dp[a]=ans
	return ans

print(lp(x))

Submission status: Runtime Error

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

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

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


def dfs(u):
    if dp[u] != 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


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

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(100000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(dfs(u) for u in lv) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(dfs(v) for v in sss))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def dfs(v):
    return max((dfs(u) for u in links[v]), default=-1) + 1


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(dfs(v) for v in sss))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            dp[i + 1][j] += dp[i][j] % mod
        if j + 1 < W and s_list[i][j + 1] == ".":
            dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)

Submission status: Runtime Error

Solution code:
# トポロジカルソート->簡単なDP
N,M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    x,y = map(int, input().split())
    adj[x-1].append(y-1) 

visited = [False] * N
topo_order = [] # sort後を格納

# topological sort by DFS
def dfs_visit(node):
    global visited, topo_order
    if visited[node]: return
    visited[node] = True
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    # 帰りがけに追加
    topo_order.append(node)
    # print(topo_order)

# topological sort main
for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]
# print("topo_order: ", topo_order)

dp = [0]*N

for node in topo_order:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node]+1)
print(max(dp))
# print(dp)

Submission status: Runtime Error

Solution code:
f=lambda:map(int,input().split())
N,M=f()
N+=1;V=[-1]*N
Q=list(range(N))
F,B=eval('{i:[]for i in Q},'*2)
for i in Q:x,y=f();F[x]+=[y];B[y]+=[x]
while Q:
 p=Q.pop();S=[1+V[q]for q in B[p]]
 if all(S)and V[p]<0:V[p]=max(S+[0]);Q+=F[p]
print(max(V))

Submission status: Runtime Error

Solution code:
f=lambda:map(int,input().split())
N,M=f()
N+=1;V=[-1]*N
Q=[*range(N)]
F,B=eval('{i:[]for i in Q},'*2)
exec('x,y=f();F[x]+=[y];B[y]+=[x];'*M)
while Q:
 p=Q.pop();S=[1+V[q]for q in B[p]]
 if all(S)and V[p]<0:V[p]=max(S+[0]);Q+=F[p]
print(max(V))

Submission status: Runtime Error

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


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    x, y = [int(elem) - 1 for elem in fin().split()]
    adj[x].append(y)

visited = [False] * N
topo_order = []
# topological sort by DFS
def dfs_visit(node):
    for neighbor in adj[node]:
        if not visited[neighbor]:
            dfs_visit(neighbor)
    topo_order.append(node)


for node in range(N):
    dfs_visit(node)
topo_order = topo_order[::-1]

dp = [0] * N
for node in topo_order[:-1]:
    for neighbor in adj[node]:
        dp[neighbor] = max(dp[neighbor], dp[node] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


T = topological_sort(G)
dist = [0] * N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v], dist[n] + 1)

print(max(dist))

Submission status: Runtime Error

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

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

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

def dfs(num_v):
    if len(graph[num_v]) == 0:
        return
    for to in graph[num_v].keys():
        dp[to] = max(dp[to], dp[num_v] + 1)
        dfs(to)

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