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: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10**5)
N, M = map(int, input().split())
G = [set() for i in range(N)]
L = [-1]*N


def solve(x, r):
    if L[x] >= 0:
        return(L[x])
    res = 0
    for z in G[x]:
        if r[z]:
            r[z] = False
            res = max(res, solve(z, r) + 1)
        else:
            res = max(res, L[z]+1)
    L[x] = res
    return(res)


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

    G[x].add(y)

r = [True]*N

for i in range(N):
    # print(L)
    if r[i]:
        L[i] = solve(i, r)
print(max(L))

# print(L)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

int1 = lambda x: int(x) - 1


def topological_sort(N, G):
    outs = defaultdict(list)
    ins = defaultdict(int)
    for v1, v2 in G:
        outs[v1].append(v2)
        ins[v2] += 1

    q = deque(v1 for v1 in range(N) if ins[v1] == 0)
    while q:
        v1 = q.popleft()
        yield v1
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)


N, M = map(int, input().split())
G = [tuple(map(int1, input().split())) for _ in range(M)]
dp = [-1] * (N + 1)  # dp[N]は親がいないときの処理用

parents = [[N] for _ in range(N)]
for v1, v2 in G:
    parents[v2].append(v1)
for x in topological_sort(N, G):
    dp[x] = max(dp[p] for p in parents[x]) + 1
print(max(dp))

Submission status: Accepted

Solution code:
# BFS的にやるDAGの最長経路
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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 = [0 for _ in range(n)]
q = deque([])

# 最長辺の候補を入れる
for i in range(n):
    if indeg[i] == 0:
        q.append(i)

while q:
    v = q.popleft()
    for w in g[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            q.append(w)
            dp[w] = max(dp[w], dp[v] + 1)

print(max(dp))

Submission status: Accepted

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

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  ins[y-1] += 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(0)
  for nxt in gra[cur] :
    ins[nxt] -= 1
    if ins[nxt] == 0 :
      mem[nxt] = mem[cur] + 1
      longest = max(longest, mem[nxt])
      q.append(nxt)

print longest

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
DP = [None for i in range(n)]
def dp(i):
    if DP[i] != None:
        return DP[i]
    ret = 0
    for j in G[i]:
        ret = max(ret, dp(j)+1)
    DP[i] = ret
    return ret
print(max([dp(i) for i in range(n)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(v):
    if(dp[v]==-1):
        dp[v]=0
        for nv in G[v]:
            dp[v]=max(dp[v],dfs(nv)+1)
    return dp[v]
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
dp=[-1]*N
res=-1
for v in range(N):
    res=max(res,dfs(v))
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(v):
    seen[v]=1
    for nv in G[v]:
        if seen[nv]:
            continue
        dfs(nv)
    topo.append(v)

N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
seen=[0]*N
topo=[]
for i in range(N):
    if not seen[i]:
        dfs(i)
dp=[0]*N
for v in reversed(topo):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

Submission status: Accepted

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)]
chl=[0]*n
for i in range(m):
    x,y=mdata()
    g[x-1].add(y-1)
    chl[y-1]=1
vis=[0]*n
for i in range(n):
    if chl[i]==0:
        s1=deque()
        s1.append(i)
        while s1:
            a=s1[-1]
            if vis[a]==1:
                if a!=i:
                    dp[par[a]]=max(dp[par[a]],dp[a]+1)
                s1.pop()
                continue
            vis[a]=1
            for j in g[a]:
                if vis[j]==0:
                    s1.append(j)
                    par[j]=a
                else:
                    dp[a]=max(dp[a],dp[j]+1)
print(max(dp))

Submission status: Accepted

Solution code:
#Longest Path 

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline

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

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

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

# print(*dp,sep="\n")
# print(*adg_list,sep="\n")

def rec(v):
    if dp[v] !=-1:
        return dp[v]
    
    nv_s = adg_list[v]

    ans = 0
    #もしnv_s(隣接する頂点の集合)が0の場合は
    #forループは実行されずに0が出力される。
    for nv in nv_s:
        ans = max(ans , rec(nv) + 1)
    dp[v] = ans
    return dp[v]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
dpv = [-1]*N

def dp(v):
    if dpv[v] != -1:
        return dpv[v]
    if len(edge[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in edge[v]:
        res = max(dp(w),res)
    res += 1
    dpv[v] = res
    return res

def solve():
    for i in range(N):
        dp(i)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve())

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, readline().split())
    graph[x].append(y)
dp = [-1] * (n + 1)


def check(v):
    if dp[v] != -1:
        return dp[v]
    if graph[v]:
        dp[v] = max(check(u) for u in graph[v]) + 1
    else:
        dp[v] = 0
    return dp[v]


print(max(check(v) for v in range(1, n + 1)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve(edge))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

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


def main():
    V, E = map(int, input().split())
    is_visited = [False] * V
    indeg = [0] * V  # 流入量
    # 隣接リスト
    G = defaultdict(lambda: [])

    for i in range(E):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        G[s].append(t)
        indeg[t] += 1

    # print(G, indeg, is_visited)
    out = []
    dp = [0] * V

    def bfs(s):
        q = deque()
        q.append(s)
        is_visited[s] = True
        while q:
            u = q.popleft()
            out.append(u)
            # print(u, out)
            for v in G[u]:
                indeg[v] -= 1
                # dp[v] = max(dp[v], dp[u] + 1)
                if indeg[v] == 0 and (not is_visited[v]):
                    q.append(v)
                    is_visited[v] = True

    def topological():
        for u in range(V):
            if indeg[u] == 0 and (not is_visited[u]):
                bfs(u)

        # print(max(dp))

    topological()

    for i in out:
        for dest in G[i]:
            dp[dest] = max(dp[dest], dp[i] + 1)

    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

V, M = map(int,input().split())
L = [[] for _ in range(V+1)]
DP = [-1 for _ in range (V + 2)]
for _ in range(M):
    x,y = map(int,input().split())
    L[x-1].append(y-1)

def rec(v):
    if DP[v] != -1: return DP[v]
    ret = 0
    for x in L[v]:
        ret = max(ret,rec(x)+1)
    DP[v] = ret
    return DP[v]
ans = 0
for i in range(V):
    ans = max(ans, rec(i))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
inf = float("inf")

n_vertices, m_edges = map(int, input().split())
edges = [[] for _ in range(n_vertices)]

for _ in range(m_edges):
    x, y = map(int, input().split())
    edges[x - 1].append(y - 1)
# print(edges)

# dp[v] := ノードvを始点としたときの有向パスの長さの最大値
# ノードvの隣接ノードv_adjに対して、dp[v] = max(dp[v], rev[v_adj] + 1)


def rec(v):
    if dp[v] != -1:
        # 既に更新済み
        return dp[v]
    for v_adj in edges[v]:
        dp[v] = max(dp[v], rec(v_adj) + 1)
    return dp[v]


dp = [-1 for _ in range(n_vertices)]
res = 0
for v in range(n_vertices):
    res = max(res, rec(v))

print(res + 1)

Submission status: Accepted

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

N,M = map(int,input().split())
p = [list(map(int,input().split())) for _ in range(M)]
dp = [-1]*N
ip = [[] for _ in range(N)]
for i in range(M):
  ip[p[i][1]-1].append(p[i][0]-1)

#閉路がないため同じ頂点は通らない
#i番目の頂点に到達するまでの最長手数をメモ化再帰で求める

def maxpath(i):
  if dp[i] != -1:
    return dp[i]
  a = 0
  for el in ip[i]:
    a = max(a,maxpath(el)+1)
  dp[i] = a
  return a
  
for i in range(N):
  maxpath(i)

print(max(dp))

Submission status: Accepted

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

#output
#便宜的にすべての点を-1しておく。
#dp[i]を頂点iから始まるpathで最長の長さとする。
#dp[i] = max(dp[v]+1)(vは頂点iから到達できる任意の頂点)

visited = [False] * N
memo = [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: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
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())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n
# dp(i):i=0,1,..,n-1:頂点iを始点とした最長のパスを返す
def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[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: Accepted

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 = [0]*n
visited = [False]*n

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in g[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: Accepted

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)
        memo[v] = res
        return res

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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)
from functools import lru_cache
sys.setrecursionlimit(10**7)
@lru_cache(maxsize=None)
def dp(v):
    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: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 10)

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

memo = {}
def dp(p):
    if p not in memo:
        memo[p] = max((1 + dp(c) for c in E[p]), default=0)
    return memo[p]

print(max(dp(p) for p in range(1, N + 1)))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 10)

N, M, *XY = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for x, y in zip(*[iter(XY)] * 2):
    E[x].append(y)

memo = {}
def dp(p):
    if p in memo:
        return memo[p]

    memo[p] = max((1 + dp(c) for c in E[p]), default=0)
    return memo[p]

print(max(dp(p) for p in range(1, N + 1)))

Submission status: Accepted

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


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


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


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

G=[[] for _ in range(N+1)]  #G[0]はダミー
for edge in range(M):
    x,y=map(int,input().split())
    G[x].append(y)

DP=[-1]*(N+1)   #DP[0]はダミー

def rec(now):
    global G
    global DP

    if DP[now]!=-1:
        return DP[now]

    else:
        res=0
        for next in G[now]:
            res=max(res,rec(next)+1)
        DP[now]=res
        return DP[now]  #resは不可


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



print(ans)

Submission status: Accepted

Solution code:
import collections
n,m = map(int,input().split())
d = {}
indegree = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    d[x-1] = d.get(x-1,[]) + [y-1]
    indegree[y-1] += 1
dp = [0]*n
q = collections.deque([i for i in range(n) if indegree[i] == 0])
while q:
    node = q.popleft()
    for nei in d.get(node,[]):
        indegree[nei] -= 1
        dp[nei] = max(dp[nei],dp[node]+1)
        if indegree[nei] == 0:
            q.append(nei)
print(max(dp))

Submission status: Accepted

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

def dfs(cur):
  if dp[cur]!=-1:
    return dp[cur]
  res=0
  for nx in G[cur]:
    res=max(res,dfs(nx)+1)
  dp[cur]=res
  return res

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

dp=[-1]*n
for i in range(n):
  dp[i]=max(dp[i],dfs(i))
print(max(dp))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
link = [[] for _ in range(n)]
inc=[0]*n
for _ in range(m):
    x,y = list(map(int,input().split()))
    link[x-1].append(y-1)
    inc[y-1]+=1

s=[]
for i in range(len(inc)):
    if inc[i]==0:
        s.append(i)
res=[]
while s:
    nxt=s.pop()
    res.append(nxt)
    for m in link[nxt]:
        inc[m]-=1
        if inc[m]==0:
            s.append(m)

path=[-1]*n
for now in res:
    if path[now]==-1:
        path[now]=0
    for nxt in link[now]:
        path[nxt] = max(path[nxt],path[now]+1)

print(max(path))

Submission status: Accepted

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

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


"""Module docstring
"""

import sys
from collections import defaultdict

sys.setrecursionlimit(pow(2, 31) - 1)

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

# def dfs(vertex: int, succ: Dict[int, List[int]], dp: Dict[int, int]) -> int:
def dfs(vertex, succ, dp):
    if vertex in dp:
        return dp[vertex]
    length = 0
    for s in succ[vertex]:
        length = max(length, 1 + dfs(s, succ, dp))
    dp[vertex] = length
    return length


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, _nb_edges) -> int:
    succ = defaultdict(list)
    for s, d in values:
        succ[s].append(d)
    # all edges have a 0 length path starting at the edge
    dp = defaultdict(lambda: -1)
    for vertex in frozenset(succ.keys()):
        if vertex in dp:
            dp[vertex] = max(dp[vertex], dfs(vertex, succ, dp))
        else:
            dp[vertex] = dfs(vertex, succ, dp)
    return max(dp.values())


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: Accepted

Solution code:
from collections import deque

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

stack = []

for u in range(N):
    if deg[u] == 0:
        stack.append(u) #入次数が0のノードをスタックに入れる
topol = []
while len(stack) != 0:
    u = stack.pop()
    topol.append(u)
    for v in G[u]:
        deg[v] -= 1
        if deg[v] == 0:
            stack.append(v)


dp = [0 for i in range(N)]
for u in topol:
    for v in G[u]:
        dp[v] = max(dp[v], dp[u]+1)
res = 0
for i in range(N):
    if res < dp[i]:
        res = dp[i]
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 9)
def solve(num):
    #base case:
    if(dic[num]==0):
        return 0

    mx = 0
    for el in dic[num]:
        if(dp[el]==-1):
            temp1 = solve(el)
            mx = max(mx, 1 + temp1)
            dp[el] = temp1
        else:
            mx = max(mx, 1 + dp[el])

    return mx

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

for _ in range(m):
    xtemp, ytemp = map(int, input().split())
    if(xtemp not in dic):
        dic[xtemp] = []
        dic[xtemp].append(ytemp)
    else:
        dic[xtemp].append(ytemp)
#init dp:
dp = [-1]*(n+1)

mxGl = 0
keys = list(dic.keys())
for node in keys:
    if(dp[node]==-1):
        temp = solve(node)
        dp[node] = temp
        mxGl = max(mxGl, temp)
    else:
        mxGl = max(mxGl, dp[node])
print(mxGl)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline

node_num, path_num = map(int, input().split())
graph = [[] for _ in range(node_num)]

for i in range(path_num):
    from_node, to_node = map(int, input().split())
    graph[from_node - 1].append(to_node - 1)
#print(graph)

#dp[i]はiを始点としたときの経路長の最大値
dp = [-1] * node_num

def rec(v):
    #print(v)
    #print(dp)
    if dp[v] > -1:
        return dp[v]
    else:
        dp[v] = 0
        for nv in graph[v]:
            dp[v] = max(dp[v], rec(nv) + 1)
        return dp[v]

ans = 0
for node in range(node_num):
    ans = max(ans, rec(node))
print(ans)

Submission status: Accepted

Solution code:


def submit():
    n, m = map(int, input().split())
    edge = {i + 1: [] for i in range(n)}
    indig = {i + 1: 0 for i in range(n)}
    dp = [-1 for _ in range(n + 1)]

    # トポロジカル順序を求める
    for _ in range(m):
        x, y = map(int, input().split())
        edge[x].append(y)
        indig[y] += 1

    indig0 = []
    for node in range(1, n + 1):
        if indig[node] == 0:
            indig0.append(node)
            dp[node] = 0

    topo = []
    while indig0:
        p = indig0.pop()
        topo.append(p)
        for e in edge[p]:
            indig[e] -= 1
            if indig[e] == 0:
                indig0.append(e)

    # トポロジカル順序に従いdpする
    for node in topo:
        for e in edge[node]:
            dp[e] = max(dp[e], dp[node] + 1)
    
    print(max(dp))

if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
from collections import deque

class Graph:
    def __init__(self,size):
        self.graph = [ {
            'idx' : i,
            'to': [],
            'inputs' : 0,
        } for i in range(size) ]

    def add_node(self,start,end):
        self.graph[start]['to'].append(end)
        self.graph[end]['inputs'] += 1

    def topological_sort(self):
        inputs = [i['inputs'] for i in self.graph]
        no_inputs = deque([ i['idx'] for i in self.graph if i['inputs'] == 0])
        ans = []
        while no_inputs:
            vertex1 = no_inputs.popleft()
            ans.append(vertex1)
            for vertex2 in self.graph[vertex1]['to']:
                inputs[vertex2] -= 1
                if inputs[vertex2] == 0:
                    no_inputs.append(vertex2)
        return ans

def main():
    n,m = map(int, input().split())
    G = Graph(n)
    for _ in range(m):
        x,y = map(int, input().split())
        G.add_node(x-1,y-1)
    tp = G.topological_sort()
    dist = [0] * n
    for v in tp[::-1]:
        for t in G.graph[v]['to']:
            if dist[v] <= dist[t]:
                dist[v] = dist[t] + 1
    print(max(dist))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def input():
    return sys.stdin.readline().strip()


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


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

dp = [-1] * n
for v in range(n):
    dp[v] = max(dp[v], dfs(v))
print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 7)


def input():
    return sys.stdin.readline().strip()


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


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

dp = defaultdict(lambda: -1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp.values()))

Submission status: Accepted

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


def input():
    return sys.stdin.readline().strip()


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


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp))

Submission status: Accepted

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

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)

Submission status: Accepted

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 -= 1
    y -= 1
    G[x].append(y)

inord = [0 for i in range(N)]
stack = []
for u in range(N):
    for v in G[u]:
        inord[v] += 1

for i in range(N):
    if inord[i] == 0:
        stack.append(i)

ans = []
while len(stack):
    u = stack.pop()
    ans.append(u)
    for v in G[u]:
        inord[v] -= 1
        if inord[v] == 0:
            stack.append(v)

#ansはtopological_sortされている

#dp[i]:i番目にたどり着くまでの最長経路
dp = [0 for i in range(N)]
for u in ans:
    for v in G[u]:
        dp[v] = max(dp[u]+1, dp[v])

ret = 0
for i in range(N):
    ret = max(ret, dp[i])
print(ret)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)
input=sys.stdin.readline

N,M=map(int,input().split())
edge={i:[] for i in range(1,N+1)}
for i in range(M):
    x,y=map(int,input().split())
    edge[x].append(y)

memo={i:-1 for i in range(1,N+1)}
for i in range(1,N+1):
    if not edge[i]:
        memo[i]=0

def long_path(start):
    if memo[start]!=-1:
        return memo[start]

    memo[start]=max(1+long_path(i) for i in edge[start])

    return memo[start]

ans=0
for i in range(1,N+1):
    ans=max(ans,long_path(i))

print(ans)

Submission status: Accepted

Solution code:

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

indeg = [0 for _ in range(N)]
outdeg = [[] for _ in range(N)]

for x, y in xy:
    x,y = x-1, y-1
    indeg[y] += 1
    outdeg[x].append(y)

heads = []
for i in range(N):
    if not indeg[i]:
        heads.append(i)

dp = [0 for _ in range(N)]
while heads:
    h = heads.pop()
    for c in outdeg[h]:
        dp[c] = max(dp[c], dp[h]+1)
        indeg[c] -= 1
        if indeg[c] == 0:
            heads.append(c)
#        print(h,c,dp)

ans = max(dp)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000000)
n,m=map(int,input().split())
v=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  v[a-1].append(b-1)

memo=[-1]*n
def dp(x):
  if memo[x]!=-1:return memo[x]
  r=0
  for i in v[x]:
    r=max(r,dp(i)+1)
  memo[x]=r
  return r
print(max(dp(i) for i in range(n)))

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
dinp = [0]*n
edges = [[]for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)
    dinp[y] += 1


next_v = deque([])
dist = [-1]*n
for i in range(n):
    if dinp[i] == 0:
        next_v.append(i)
        dist[i] = 0
ans = 0
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        dinp[v2] -= 1
        if dinp[v2] != 0:
            continue
        next_v.append(v2)
        if dist[v]+1 <= dist[v2]:
            continue
        dist[v2] = dist[v]+1
        ans = max(ans, dist[v2])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
dinp = [0]*n
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)
    dinp[y] += 1

queue = deque([])
for i in range(n):
    if dinp[i] == 0:
        queue.append(i)

toposorted = []
while queue:
    v = queue.popleft()
    toposorted.append(v)
    for v2 in edges[v]:
        dinp[v2] -= 1
        if dinp[v2] == 0:
            queue.append(v2)

dist = [0]*n
for i in range(n):
    v = toposorted[i]
    for v2 in edges[v]:
        if dist[v2] <= dist[v]-1:
            continue
        dist[v2] = dist[v]-1
print(-min(dist))

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
dd = defaultdict(int)
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)
    dd[y] += 1

queue = deque([])
for i in range(n):
    if dd[i] == 0:
        queue.append(i)

toposorted = []
while queue:
    v = queue.popleft()
    toposorted.append(v)
    for v2 in edges[v]:
        if dd[v2] <= 0:
            continue
        dd[v2] -= 1
        if dd[v2] == 0:
            queue.append(v2)

dist = [0]*n
for i in range(n):
    v = toposorted[i]
    for v2 in edges[v]:
        if dist[v2] <= dist[v]-1:
            continue
        dist[v2] = dist[v]-1
print(-min(dist))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)


def memoize(f):
    memo = [-1]*n

    def memoized(args):
        if memo[args] != -1:
            return memo[args]
        else:
            memo[args] = f(args)
            return memo[args]
    return memoized


@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


ans = 0
for i in range(n):
    ans = max(ans, longest_path(i))
print(ans)