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 sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 6)
xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=None)
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: Accepted

Solution code:
import sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 7 + 1)
xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=None)
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: Accepted

Solution code:
import sys
import collections
from functools import lru_cache

xy = []
d = collections.defaultdict(list)
@lru_cache(maxsize=None)
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
    sys.setrecursionlimit(10 ** 5 + 1)
    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: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split())
d=[[] for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    d[x-1].append(y-1)
dp=[0 for i in range(N)]

def depth(now,score,d):
    global dp
    if dp[now]==0 or not(dp[now]):
        if d[now]:
            _score=[]
            for i in d[now]:
                _score.append(depth(i,score+1,d)-score)
            dp[now]=max(_score)
        else:
            return score

        return dp[now]+score

    else:
        return dp[now]+score



Max=0
for i in range(N):
    m=depth(i,0,d)
    if  m>Max:            
        Max=m
print(Max)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

graph = [[] for _ in range(N)]
indegree = [0 for _ in range(N)]

for i in range(M):
    graph[edge[i][0]-1].append(edge[i][1]-1)
    indegree[edge[i][1]-1] += 1

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

dp = [0]*N

while queue:
    node = queue.popleft()
    for adj in graph[node]:
        indegree[adj] -= 1
        if indegree[adj] == 0:
            queue.append(adj)
            dp[adj] = dp[node]+1

print(max(dp))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
m = map(int,read().split())
XY = zip(m,m)

in_edge = [[] for _ in range(N+1)]
out_edge = [[] for _ in range(N+1)]
for x,y in XY:
    out_edge[x].append(y)
    in_edge[y].append(x)

out_deg = [len(x) for x in out_edge]

stack = [i for i,x in enumerate(out_deg[1:],1) if x==0]

dp = [0] * (N+1)
while stack:
    c = stack.pop()
    for p in in_edge[c]:
        y = dp[c]+1
        if dp[p] < y:
            dp[p] = y
        out_deg[p] -= 1
        if not out_deg[p]:
            stack.append(p)

answer = max(dp)
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def main():
    N, M = map(int, input().split())
    d = {}
    for _ in range(M):
        x, y = map(int, input().split())
        if x in d:
            d[x].append(y)
        else:
            d[x] = [y]
    l = {}
    m = 0
    for i in d:
        m = max(m, dfs(i, d, l))
    print(m)
def dfs(node, d, l):
    if node in l:
        return l[node]
    if node not in d:
        return 0
    a = 1 + max(dfs(i, d, l) for i in d[node])
    l[node] = a
    return a

main()

Submission status: Accepted

Solution code:
import sys

def dp(i, xy, l):
    if l[i] >= 0:
        return l[i]
    l[i] = t = max(dp(j, xy, l) for j in xy[i]) + 1
    return t

def main():
    sys.setrecursionlimit(10 ** 6)
    N, M = map(int, input().split())
    xy = [set() for _ in range(N)]
    for _ in range(M):
        xi, yi = map(int, input().split())
        xy[xi - 1].add(yi - 1)
    l = [0 if not i else -1 for i in xy]
    m = 0
    for i in range(N):
        m = max(m, dp(i, xy, l))
    print(m)


main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
xy = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# その頂点に向かう辺の数
V = [0] * (N + 1)

for x, y in zip(xy, xy):
    graph[x].append(y)
    V[y] += 1

# その頂点に向かう辺がない頂点
start = [i for i, name in enumerate(V) if name == 0]

# 頂点iを終点とする最長パスの長さ
dp = [0] * (N + 1)
queue = []

while start:
    v = start.pop()
    for go in graph[v]:
        V[go] -= 1
        if V[go] == 0:
            start.append(go)
        dp[go] = max(dp[go], dp[v] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, sys
input = sys.stdin.readline
n, m = [ int(v) for v in input().split() ]
edge = []
in_list = [0] * n
out_list = [0] * n
dp_list = [0] * n
connect_list = [ [] for i in range(n) ] 

for i in range(m):
    s, t = [ int(v)-1 for v in input().split() ]
    edge.append((s,t))
    in_list[t] += 1
    out_list[s] += 1
    connect_list[t].append(s)

search_list = [ i for i, v in enumerate(out_list) if v == 0 ]
while search_list:
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:
            out_list[j] -= 1
            if dp_list[j] < dp_list[i] + 1:
                dp_list[j] = dp_list[i] + 1
            if out_list[j] == 0:
                new_search_list.append(j)
    search_list = new_search_list

print(max(dp_list))

Submission status: Accepted

Solution code:
n, m = [ int(v) for v in input().split() ]
edge = []
in_list = [0] * n
out_list = [0] * n
dp_list = [0] * n
connect_list = [ [] for i in range(n) ] 

for i in range(m):
    s, t = [ int(v)-1 for v in input().split() ]
    edge.append((s,t))
    in_list[t] += 1
    out_list[s] += 1
    connect_list[t].append(s)

search_list = [ i for i, v in enumerate(out_list) if v == 0 ]
while search_list:
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:
            out_list[j] -= 1
            if dp_list[j] < dp_list[i] + 1:
                dp_list[j] = dp_list[i] + 1
            if out_list[j] == 0:
                new_search_list.append(j)
    search_list = new_search_list

print(max(dp_list))

Submission status: Accepted

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


dp = [-1]*100100
def rec(v, G):
    if dp[v]!=-1:
        return dp[v]
    
    cnt = 0
    for nv in G[v]:
        cnt = max(cnt, rec(nv, G) + 1)
    
    dp[v] = cnt
    return dp[v]


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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, M = [int(i) for i in input().split()]
edges = {j : [] for j in range(N + 1)}
for j in range(M):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    edges[x].append(y)
for i in range(N):
    edges[N].append(i)

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


def dfs(last):
    if memo_ls[last] is not None:
        return memo_ls[last]
    if len(edges[last]) == 0:
        return 0
    cnt = max([dfs(_next) + 1 for _next in edges[last]])
    memo_ls[last] = cnt
    return cnt


print(dfs(N) - 1)

Submission status: Accepted

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

path = [[] for _ in range(N)]
pin = [0]*N
for _ in range(M):
  ip,op = map(int,input().split())
  pin[op-1]+=1
  path[ip-1].append(op-1)

cur = []
for i in range(N):
  if pin[i]==0:
    cur.append(i)

ans = 0
while cur:
  ans += 1
  nxt = []
  for ip in cur:
    for op in path[ip]:
      pin[op] -= 1
      if pin[op]==0 and not(op in nxt):
        nxt.append(op)
  cur = [x for x in nxt]
print(ans-1)

Submission status: Accepted

Solution code:
import sys
#許容す再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# 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)]
    for _ in range(M):
        x,y = map(int,input().split())
        #最初のindexをゼロとする
        lst_edge[x-1].append(y-1)
    
    #dp[v] :: ノードvを始点とした時の有向パスの長さの最大値
    # -1で初期化
    dp = [-1]*N

    #メモ化再帰
    def rec(v):
        #すでに更新済み
        if (dp[v] != -1):
            return dp[v]
        ans = 0
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            ans = chmax(ans,rec(nv)+1)
        dp[v] = ans
        return dp[v]
      

    # 全ての点に対して更新する
    ans = 0
    for v in range(N):
        ans = chmax(ans,rec(v))

    print(ans)

main()

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
edge = [[] for _ in range(N)] #edge[x]:xから到達できる頂点のリスト
deg = [0]*N #deg[v]:頂点vに入ってくる辺の数
for _ in range(M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
    deg[y-1] += 1

#topological sort (order:V+E)
from collections import deque
ans = list(v for v in range(N) if deg[v]==0)
deq = deque(ans)
while deq:
    v = deq.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t] == 0:
            deq.append(t)
            ans.append(t)
            
#ans:topological sort された頂点

dp = [0]*N
ans.reverse()
for i in range(N):
    if edge[ans[i]]:
        for v in edge[ans[i]]:
            dp[ans[i]] = max(dp[ans[i]], dp[v]+1)
            
print(max(dp))

Submission status: Accepted

Solution code:
import sys

N, M = [int(s) for s in input().split()]
sys.setrecursionlimit(10**5)
dp = [-1] * (N+1)
neighbors = [[] for _ in range(N+1)]

for _ in range(M):
    x, y = [int(s) for s in input().split()]
    neighbors[x].append(y)

def LP(v):
    if dp[v] != -1:
        return dp[v]
    else:
        res = 0
        lp = [-1]
        for nv in neighbors[v]:
            lp.append(LP(nv))
        res = max(res, max(lp) + 1)
        dp[v] = res
        return res

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

print(ans)

Submission status: Accepted

Solution code:
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

import sys
sys.setrecursionlimit(10**5)
N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)

Submission status: Accepted

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


dp = [-1]*n #dp[i]はiからスタートした有向pathのうち最長のものの長さ
#print(graph)
def solve(i):
    if dp[i] != -1:#既に計算済み
        return dp[i]
    if len(graph[i]) == 0:#iが葉であるとき
        dp[i] = 0
        return 0
    max_length = 0
    for next_node in graph[i]:
        dp[next_node] = solve(next_node)
        max_length = max(max_length,dp[next_node])

    dp[i] = max_length + 1
    return dp[i]

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


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    dp = [-1]*(N+1)
    # G = [[0] * (N+1) for i in range(N+1)]
    G = [[] for i in range(N+1)]
    for i in range(M):
        G[x[i]].append(y[i])

    def rec(v : int):
        if dp[v] != -1:
            return dp[v]
        
        t = 0
        for i in G[v]:
            t = max(t, rec(i)+1)
        dp[v] = t

        return dp[v]

    res = 0
    for i in range(1,N+1):
        res = max(res, rec(i))
    print(res)



    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    solve(N, M, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N,M = map(int,input().split())
E = [[] for _ in range(N)]
for i in range(M):
  x,y = map(int,input().split())
  x -= 1
  y -= 1
  E[x].append(y)
#print(E)

# dp[i]:頂点iを始点とする最長パスの長さ
dp = [-1 for _ in range(N)]

def rec(v):
  if dp[v] != -1:
    return dp[v]
  res = 0
  for u in E[v]:
    res = max(res, rec(u)+1)
  dp[v] = res
  return dp[v]

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

Submission status: Accepted

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):
    global dp
    if dp[n] >= 0:
        return dp[n]

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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):
    global dp
    if dp[n] > 0:
        return dp[n]

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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):
    global dp
    if dp[n] > 0:
        return dp[n]

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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)
in_num = defaultdict(int)

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

q = deque()

for n in range(N):
    if in_num[n] == 0:
        q.append(n)


DP = [0] * N

while q:
    v = q.popleft()
    t = T[v]
    for y in t:
        in_num[y] -= 1
        if in_num[y] == 0:
            q.append(y)
            DP[y] = max(DP[y], DP[v]+1)


print(max(DP))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**9)

n,e = [int(i) for i in input().split()]
mat = [[] for i in range(n)]
for i in range(e):
    a,b = [int(i) for i in input().strip().split()]
    mat[a-1].append(b-1)

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

def cal(i):  
    if mat[i]==[]:
        return 0
    else:
        if dp[i]==-1:
            nei = mat[i]
            dp[i] = max([1+cal(j) for j in nei])
        return dp[i]


m=0
for i in range(n):
    if dp[i]==-1:
        m=max(m,cal(i))
print(m)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

# 木構造を作る
N, M  = map(int, input().split())

G = [[] for i in range(N)]
for i in range(M):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[u-1].append((v-1))

cnt_in = defaultdict(int)
outs = defaultdict(list)
for vs in G:
    for v in vs:
        cnt_in[v] += 1
# print(cnt_in)
res = []
q = deque([i for i in range(N) if cnt_in[i]==0])
dp = [0]*(N+1)
# トポロジカルソートで、入次数を削っていくときに
# 入次数がゼロになったときに追加する
while len(q) > 0:
    v = q.popleft()
    res.append(v)
    for next_v in G[v]:
        cnt_in[next_v] -= 1
        if cnt_in[next_v] == 0:
            q.append(next_v)
            dp[next_v] = max(dp[next_v], dp[v] + 1)

print(max(dp))

Submission status: Accepted

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

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

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

dp = [-1]*(N+1)

def saiki(v):
    if dp[v]!=-1: return dp[v]
    res = 0
    for u in to[v]:
        res=max(res,saiki(u)+1)
    dp[v]=res
    return res

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

Submission status: Accepted

Solution code:
def tpsort(n,lst):
    parent=[0]*(n+1)
    child=[[] for _ in range(n+1)]
    for p,c in lst:
        child[p].append(c)
        parent[c]+=1
    ans=[]
    que=[]
    for i in range(1,n+1):
        if parent[i]==0:
            que.append(i)
    while que:
        h=que.pop()
        ans.append(h)
        for u in child[h]:
            parent[u]-=1
            if parent[u]==0:
                que.append(u)
    return ans
N,m=map(int,input().split())
data=[list(map(int,input().split())) for i in range(m)]
t=[[] for i in range(N+1)]
for p,c in data:
    t[p].append(c)
s=tpsort(N,data)
dp=[0]*(N+1)
for v in s:
    for r in t[v]:
        dp[r]=max(dp[v]+1,dp[r])
print(max(dp))

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    elif len(edge[s]) == 0:
        dp[s] = 0
        return 0
    else:
        res = 0
        for v in edge[s]: 
            res = max(res,dfs(v)+1)
        dp[s] = res
        return res
n,m = LI()
dp = [-1]*n
edge = [[] for _ in range(n)]
for _ in range(m):
    x,y = LI()
    x -= 1
    y -= 1
    edge[x].append(y)

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

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    elif len(edge[s]) == 0:
        return 0
    else:
        res = 0
        for v in edge[s]: 
            res = max(res,dfs(v)+1)
        dp[s] = res
        return res
n,m = LI()
dp = [-1]*n
edge = [[] for _ in range(n)]
for _ in range(m):
    x,y = LI()
    x -= 1
    y -= 1
    edge[x].append(y)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
N,M = [int(x) for x in input().split()]
E ={i: [] for i in range(1, N+1)}
for _ in range(M):
  u,v = [int(x) for x in input().split()]
  E[u].append(v)
#print(E)
dp =[-1]*(N+1)
def memo(v):
  if dp[v]!= -1:
    return dp[v]
  res = 0
  for nv in E[v]:
    res = max(res,memo(nv)+1)
  dp[v] =res
  return dp[v]
res = 0
for v in range(1,N+1):
  res = max(res,memo(v))
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000 + 1)

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

maxDist = [0 for i in range(N+1)]
in_degree = [0 for i in range(N+1)]
adj_list = [[] for i in range(N+1)]

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

for node in range(1, N+1):
    adj_list[0].append(node)
    in_degree[node] += 1

# dp[i] = maximum length of path ending at i
flattenedNodes = []
def dfs(node):
    for child in adj_list[node]:
        maxDist[child] = max(maxDist[child], 1 + maxDist[node])
        in_degree[child] -= 1
        if in_degree[child] == 0:
            dfs(child)
            
dfs(0)
print(max(maxDist) - 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100001)

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

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

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

def dfs(node):
    if dp[node] > 0:
        return dp[node]
    mx = 0
    for i in g[node]:
        a = dfs(i) + 1
        if mx < a:
            mx = a
    dp[node] = mx
    return mx

ans = 0
for i in range(N):
    if dp[i] == 0:
        ans = max(ans, dfs(i))

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def dfs(v):
    if d[v] != -1:
        return d[v]
    res = -1
    for u in e[v]:
        res = max(res, dfs(u))
    res += 1
    d[v] = res
    return res


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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(n)]
rev_Edg = [[] for _ in range(n)]
deg = [len(rev_Edg[i]) for i in range(n)]


Root_check = [1]*n
Dist = [0]*n
for i in range(m):
    v1,v2 = map(int, sys.stdin.readline().split( ))
    v1-=1
    v2-=1
    Edg[v1].append(v2)
    rev_Edg[v2].append(v1)
    deg[v2] += 1
    Root_check[v2] = 0
    

Q =deque()
for i in range(n):
    if Root_check[i] == 1:
        Q.append(i)

while len(Q) > 0:
    v = Q.popleft()
    for w in Edg[v]:
        Dist[w] = max(Dist[w],Dist[v] +1)####
        deg[w] -=1 ############
        if deg[w] == 0:##########
            Q.append(w)###########
            


print(max(Dist))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

input = sys.stdin.readline

inf = float('inf')


def rec(v):
    if used[v]:
        return dp[v]
    used[v] = True
    res = 0
    for u in es[v]:
        res = max(res, rec(u) + 1)
    dp[v] = res
    return res


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

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

used = [False] * n
dp = [inf] * n

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# from functools import lru_cache


def main():
    N, M = LI()
    es = [[x for x in LI()] for _ in range(M)]

    from collections import defaultdict
    outs = defaultdict(list)  # ノードが int なら、[[] for _ in range(n+1)] でもよさそう。
    # ins = defaultdict(int)    # ノードが int なら、 [0 for _ in range(n+1)] でもよさそう。
    for from_v, to_v in es:
        outs[from_v].append(to_v)
        # ins[to_v] += 1

    # @lru_cache()
    memo = [None for _ in range(N+1)]
    def max_len(v):
        if memo[v] is not None:
            return memo[v]

        if not outs[v]:
            memo[v] = 0
            return 0
        else:
            memo[v] = max([max_len(x)+1 for x in outs[v]])
            return memo[v]

    print(max([max_len(x) for x in range(1,N+1)]))


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    # 入力
    N, M = LI()
    es = [[x for x in LI()] for _ in range(M)]
    all_v = list(range(1, N+1))

    # まず、outs, ins を定義する。
    # outs はグラフの関連リスト表記。
    # outs = {node1: [node2, node3, ...], node2: [...], ...}
    # ins は、そのノードに入る辺の本数。
    # ins  = {node1: 1, node2: 2, ...}

    from collections import defaultdict

    outs = defaultdict(list)  # ノードが int なら、[[] for _ in range(n+1)] でもよさそう。
    ins = defaultdict(int)    # ノードが int なら、 [0 for _ in range(n+1)] でもよさそう。
    for from_v, to_v in es:
        outs[from_v].append(to_v)
        ins[to_v] += 1


    # つぎに、探索キューを初期化する。
    # ノードを全探索し、ins が 0 のものを探索キューに入れておく。

    from collections import deque
    q = deque()
    for v in all_v:
        if ins[v] == 0:
            q.append((v, 0))  # node, depth


    # トポロジカルソート本体（要は幅優先探索）

    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append((v2, depth+1))
                depth_max = max(depth_max, depth+1)


    # # 結果
    # print(res)  # ソート済みリスト

    # # 閉路判定（閉路はあるか？）
    # print(False if len(res) == n else True)  # res の長さがノード数と一致していたら、閉路なし。そうでなければ閉路あり。

    # 最大の深さ：深さの情報も同時に埋め込んでおく（上のコードにはもう埋め込んである）。
    print(depth_max)


main()

Submission status: Accepted

Solution code:
from collections import deque

def main(n, edges):
    deg = [0] * (n + 1)
    adj = {}

    for j in range(1, n + 1):
        adj[j] = []

    for u, v in edges:
        adj[u].append(v)
        deg[v] += 1

    S = deque()

    dp = [-1] * (n + 1)

    for u in range(1, n + 1):
        if deg[u] == 0:
            S.append(u)
            dp[u] = 0

    L = []

    while S:
        v = S.popleft()
        L.append(v)
        for u in adj[v]:
            deg[u] -= 1
            if deg[u] == 0:
                S.append(u)
                dp[u] = max(dp[u], dp[v] + 1)

    return max(dp)

assert main(6, [ (2, 3), (4, 5), (5, 6) ]) == 2
assert main(4, [ (1, 2), (1, 3), (3, 2), (3, 4), (2, 4) ]) == 3

n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))
ans = main(n, edges)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int,input().split())
edges = [[int(e)-1 for e in input().split()] for _ in range(M)]
ad = [[] for _ in range(N)]
num = [0] * N
for x, y in edges:
    ad[x].append(y)
    num[y] += 1

S = deque()
L = []
dp = [-1] * N

for v in range(N):
    if num[v] == 0:
        S.append(v)
        dp[v] = 0

while S:
    v = S.popleft()
    L.append(v)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
        dp[nv] = max(dp[nv], dp[v] + 1)

ans = max(dp)
print(ans)

Submission status: Accepted

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

    N,M = map(int,input().split())
    dp = [-1]*N
    ad = [deque() for _ in range(N)]
    num = [0]*N
    for _ in range(M):
        x,y = map(int,input().split())
        x -= 1; y -= 1
        ad[x].append(y)
        num[y] += 1

    L = []
    S = deque()

    for v in range(N):
        if num[v] == 0:
            S.append(v)
            dp[v] = 0

    while S:
        v = S.popleft()
        L.append(v)
        for _ in range(len(ad[v])):
            nv = ad[v].popleft()
            num[nv] -= 1
            if num[nv] == 0:
                S.append(nv)
                dp[nv] = dp[v] + 1

    ans = max(dp)
    print(ans)

main()