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
sys.setrecursionlimit(10000)

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

def rec(v):
    if dp[v] >= 0:
        return dp[v]
    temp = 0
    for next in graph[v]:
        temp = max(rec(next) + 1, temp)
    dp[v] = temp
    return temp

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
def tsort(n,g,inc):
    s,tsl=deque(),[]
    s.extend([i for i,x in enumerate(inc) if x==0])
    while len(s)>0:
        x=s.popleft()
        tsl.append(x)
        for y in g[x]:
            inc[y]-=1
            if inc[y]==0:s.append(y)
    return tsl
def main():
    N,M=tuple(map(int,sys.stdin.readline().split()))
    lpl,inc,g=[0 for _ in range(N)],[0 for _ in range(N)],[[] for _ in range(N)]
    for _ in [0]*M:
        x,y=tuple(map(int,sys.stdin.readline().split()))
        inc[y-1]+=1
        g[x-1].append(y-1)
    tsl=tsort(N,g,inc)
    for t in tsl:
        for n in g[t]:lpl[n]=lpl[t]+1 if lpl[t]+1>lpl[n] else lpl[n]
    print(max(lpl))
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
# Longest path
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1)
dp = [-1 for _ in range(N)]

def rec(c):
    if dp[c] != -1:
        return dp[c]
    res = 0
    for i in graph[c]:
        res = max(res, rec(i) + 1)
    dp[c] = res
    return res

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
dp=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)

def dfs(s):
  if edge[s]:
    for i in edge[s]:
      if dp[i]:dp[s]=max(dp[s],dp[i]+1)
      else:dp[s]=max(dp[s],dfs(i)+1)
    return dp[s]
  else:return 0
for i in range(n):
  dfs(i)
print(max(dp))

Submission status: Accepted

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

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve0(N, M, edges):
    path = edges.copy()
    exists = 1
    for i in range(2, M + 1):
        next_path = defaultdict(set)
        for v1 in path:
            for v2 in path[v1]:
                if edges[v2]:
                    next_path[v1].update(edges[v2])
                    exists = i
                    # debug(": i, v1, next_path[v1]", i, v1, next_path[v1])
        if exists != i:
            # no more pathes
            break
        path = next_path
    return exists


def solve(N, M, edges):
    longest = {}

    def get_longest(start):
        if longest.get(start) != None:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def solve(N, M, edges):
    import numba
    longest = [-1] * (N + 1)

    def intlist(xs):
        if xs:
            return list(xs)
        else:
            return numba.typed.List()

    edges = [intlist(edges[k]) for k in range(N + 1)]
    @numba.njit
    def get_longest(start, edges):
        if longest[start] != -1:
            return longest[start]

        ret = 0
        for v in edges[start]:
            x = get_longest(v, edges) + 1
            if x > ret:
                ret = x
        longest[start] = ret
        return ret

    ret = 0
    for v in range(N + 1):
        x = get_longest(v, edges)
        if x > ret:
            ret = x
    return ret


def solve(N, M, edges):
    longest = [-1] * (N + 1)

    for i in range(N + 1):
        if not edges[i]:
            longest[i] = 0

    def get_longest(start):
        next = edges[start]
        for v in next:
            if longest[v] == -1:
                longest[v] = get_longest(v)

        ret = max(longest[v] for v in next) + 1
        return ret

    for i in range(N + 1):
        if longest[i] == -1:
            longest[i] = get_longest(i)

    return max(longest[v] for v in edges)


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""

T2 = """
6 3
2 3
4 5
5 6
"""

T3 = """
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


def _test():
    """
    # >>> as_input(T1)
    # >>> main()
    # 3

    # >>> as_input(T2)
    # >>> main()
    # 2

    >>> as_input(T3)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def topological_sort(vertex:list, edge:list):
    graph = {i: [] for i in vertex}
    for i, j in edge:
        graph[i].append(j)
        
    inp_cnt = defaultdict(int)
    outs = defaultdict(list)
    for inp, out in edge:
        inp_cnt[out] += 1
        outs[inp].append(out)

    result = []
    queue = deque([i for i in vertex if inp_cnt[i]==0])
    while queue:
        v = queue.popleft()
        result.append(v)
        for v2 in outs[v]:
            inp_cnt[v2] -= 1
            if inp_cnt[v2] == 0:
                queue.append(v2)
    return result

N, M = map(int, input().split())
vertex = list(range(1, N+1))
edge = [list(map(int, input().split())) for _ in range(M)]
graph = {i: [] for i in vertex}
for i, j in edge:
    graph[i].append(j)

sorted_vertecies = topological_sort(vertex, edge)
dp = [0] * (N+1)
for i in sorted_vertecies:
    ends = graph[i]
    for j in ends:
        dp[j] = max(dp[j], dp[i] + 1)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = map(int, input().split())
    nodes[end -1].append(start-1)

for i in range(edges):
    if not len(nodes[i]):
        dp[i] = 0
def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque

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


grafo = [[] for i in range(n+1)]

num_adj = [0] * (n+1)

for i in range(m):
    u, v = map(int,input().split())
    grafo[u].append(v)
    num_adj[v] += 1

q = deque()

for i in range(1, n+1):
    if num_adj[i] == 0:
        q.append(i)

dp = [0] * (n + 1)

while q:
    n = q.popleft()
    for s in grafo[n]:
        num_adj[s] -= 1

        if num_adj[s] == 0:
            q.append(s)
            dp[s] = dp[n] + 1

print(max(dp))

Submission status: Accepted

Solution code:
def main():
    n, adj = getInputs()
    sequence = getTopologicalSort(n, adj)

    distance = [-1] * n
    longest = -1

    for v in sequence:
        if len(adj[v]) == 0:
            distance[v] = 0
        else:
            for dest in adj[v]:
                distance[v] = max(distance[v], 1 + distance[dest])
                longest = max(longest, distance[v])

    print(longest)

def getTopologicalSort(n, adj):
    state = [0] * n
    toVisit = list(range(n))

    topologicalSort = []
    order = []

    while len(toVisit) > 0:
        curr = toVisit.pop()

        if state[curr] == 0:
            order.append(curr)
            state[curr] = 1

            foundNewDest = False
            for dest in adj[curr]:
                if state[dest] == 0:
                    toVisit.append(dest)
                    foundNewDest = True

            if not foundNewDest:
                while True:
                    v = order[-1]

                    allProcessed = True
                    for dest in adj[v]:
                        if state[dest] == 0:
                            allProcessed = False
                            break

                    if allProcessed:
                        state[v] = 2
                        topologicalSort.append(order.pop())

                    if len(order) == 0 or not allProcessed:
                        break

    return topologicalSort

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

main()

Submission status: Accepted

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

dp = [0] * n
s = []
for i in range(n):
    if not enter[i]:
        s.append(i)

while(s!=[]):
    v = s.pop(0)
    for i in G[v]:
        enter[i] -= 1
        if not enter[i]:
            s.append(i)
            dp[i] = dp[v]+1

print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())

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

q = deque()

for i in range(1, n + 1):
    if deg[i] == 0:
        q.append(i)

dp = [0] * (n + 1)
while q:
    n = q.popleft()
    for zzz in g[n]:
        deg[zzz] -= 1
        if deg[zzz] == 0:
            q.append(zzz)
            dp[zzz] = dp[n] + 1

print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = map(int, input().split())
    nodes[end -1].append(start-1)

def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print(max(dp))

Submission status: Accepted

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
XY = [LI() for _ in range(M)]

w = [None] * N
links = [[] for _ in range(N)]
visit = [False] * N


def create_links():
    for x, y in XY:
        links[x - 1].append(y - 1)


def dfs(u):
    visit[u] = True
    n = 0
    for v in links[u]:
        if not visit[v]:
            w[v] = dfs(v)
        n = max(n, w[v])
    return n + 1


def main():
    create_links()
    for i in range(N):
        if not visit[i]:
            w[i] = dfs(i)
    ans = max(w) - 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)

ds = {}
def sub(u):
    if u in ds:
        return ds[u]
    d = 0
    for v in ns[u]:
        d = max(d, sub(v)+1)
    ds[u] = d
    return d

for i in range(n):
    if i not in ds:
        sub(i)
print(max(ds.values()))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def dfs(start):
    q = [start]
    d0 = 0
    d1 = 0
    while q:
        u = q.pop()
        if u>=0:
            if seen[u]:
                continue
            seen[u] = d0
            d0 += 1
            q.append(~u)
            for v in ns[u]:
                if seen[v] is None:
                    q.append(v)
        else:
            if ns[~u]:
                done[~u] = max(done[v] for v in ns[~u]) + 1
            else:
                done[~u] = 0

n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)

# 行きがけ順
seen = [None] * n
# 帰りがけ順
done = [None] * n
    
for i in range(n):
    if seen[i] is not None:
        continue
    dfs(i)
print(max(done))

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 = map(lambda x: int(x)-1, input().split())
    edges[x].append(y)


def dfs(v, parent):
    if visited[v]:
        return
    visited[v] = 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)
        if dist[v] >= dist[v2]+1:
            continue
        dist[v] = dist[v2]+1


dist = [0]*n
visited = [0]*n

for i in range(n):
    if visited[i]:
        continue
    dfs(i, -1)

print(max(dist))

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
deg = [0]*(n+1)
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    deg[v] += 1
q = deque()

for i in range(1, n+1):
    if deg[i] == 0:
        q.append(i)

dp = [0]*(n+1)
while q:
    n = q.popleft()
    for s in graph[n]:
        deg[s] -= 1
        if deg[s] == 0:
            q.append(s)
            dp[s] = dp[n]+1

print(max(dp))

Submission status: Accepted

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

from collections import deque
topo = [0]
deq = deque(topo)

while deq:
    v = deq.popleft()
    for t in G[v]:
        deg[t] -= 1
        if deg[t] == 0:
            topo.append(t)
            deq.append(t)

dp = [-1] * (N+1)
for v in topo:
    for t in G[v]:
        dp[t] = max(dp[t], dp[v] + 1)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
graph={}
n,m=map(int,input().split())
for i in range(1,n+1):
    graph[i]=[]
for _ in range(m):
    u,v=map(int,input().split())
    graph[u].append(v)

def dfs(i,dp):
    temp=0
    if dp[i]!=-1:
        return dp[i]
    for nvr in graph[i]:
        temp=max(temp,dfs(nvr,dp)+1)
    dp[i]=temp
    return temp 

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

Submission status: Accepted

Solution code:
import sys

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

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

    # 隣接リストを作成
    adjacencyList = [[] for _ in range(N)]

    # 距離の情報
    dp = [0] * N

    # 入次数　（いりじすう）
    deg = [0] * N

    for _ in range(M):
        v, nv = map(int, input().split())
        adjacencyList[v-1].append(nv-1)
        #　入次数に1を足す
        deg[nv-1] += 1

    queue = []

    # BFS探索
    # 入次数がゼロの頂点から探索を始める
    for v in range(N):
        if deg[v] == 0:
            queue.append(v)

    while queue:
        # 現在の頂点をqueueからpop
        v = queue.pop(0)
        for nv in adjacencyList[v]:
            # 探索済みの頂点の入次数を減らす
            deg[nv] -= 1

            # 完全に探索済みの頂点の入次数がゼロの時、経路の距離を出発点から計算
            if deg[nv] == 0:
                # 頂点をqueueに追加する
                queue.append(nv)
                dp[nv] = max(dp[v] + 1, dp[nv])

    print(max(dp))
    
main()

Submission status: Accepted

Solution code:
import sys
import collections
# input処理を高速化する
input = sys.stdin.readline
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
    # For sequences, (strings, lists, tuples), use the fact that empty sequences are false.
    # https://www.python.org/dev/peps/pep-0008/#programming-recommendations
    while 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] = max(dp[nv], dp[v] + 1)
    print(max(dp))
main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)


@lru_cache(maxsize=None)
def rec(node):
    if len(graph[node]) == 0:
        return 0
    ans = 0
    for after in graph[node]:
        ans = max(ans, rec(after) + 1)
    return ans


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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
#print(sys.getrecursionlimit())
n,m=map(int,input().split())
dp=[-1]*n
E=[ [] for i in range(n) ]

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

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

res=0
for v in range(n):
  res=max(res,rec(v))
print(res)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

dp=[-1]*100100
G=[[] for _ in range(100100)]

def dfs(v):
  if dp[v]!=-1:
    return dp[v]

  x=0
  for w in G[v]:
    r=dfs(w)+1
    x=max(x,r)

  dp[v]=x
  return x

def main():
  n,k=LI()
  for _ in range(k):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)

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

  return ans

# main()
print(main())

Submission status: Accepted

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

N,M = map(int,readline().split())
G = [[] for i in range(N)]
indegree = [0 for i in range(N)]

for i in range(M):
  x,y = map(int,readline().split())
  G[x - 1].append(y - 1)
  indegree[y - 1] += 1
  
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)
    
cnt = -1
while stack:
  cnt += 1
  newstack = []
  while stack:
    v = stack.pop()
    for child in G[v]:
      indegree[child] -= 1
      if indegree[child] == 0:
        newstack.append(child)
  stack = newstack

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  # どこからくるかとういう情報
  path[y-1].append(x-1)

memo = [-1]*n
def dfs(v):
  if memo[v] < 0:
    if len(path[v])==0:
      memo[v]=0
    else:
      memo[v]=max([dfs(p)+1 for p in path[v]])
  return memo[v]

res = 0
for i in range(n):
  tmp = dfs(i)
  if res < tmp:
    res = tmp
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
(n,m),*xy = [list(map(int,r.split())) for r in open(0)]
g = [[] for _ in range(n)]
dp = [0 for _ in range(n)]

for i in xy:
    x,y = i[0],i[1]
    x -= 1
    y -= 1
    g[y].append(x)

def rec(node):
    if dp[node] > 0:
        return dp[node]
    
    if not g[node]:
        dp[node] = 0
        return 0

    for child in g[node]:
        dp[node] = max(dp[node], rec(child) + 1)

    return dp[node]

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dfs(n,arr,visited):
    for i in graph[n]:
        if visited[i]==False:
            arr[n]=max(arr[n],dfs(i,arr,visited)+1)
            visited[i]=True
        else:
            arr[n]=max(arr[n],arr[i]+1)
    return arr[n]

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

graph=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    if a!=b:
        graph[a-1].append(b-1)

visited=[False for i in range(n)]

arr=[0 for i in range(n)]

for i in range(n):
    if visited[i]==False:
        dfs(i,arr,visited)
print(max(arr))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
n,m=map(int,input().split())
adjacent_list=[[] for i in range(n+1)]
for i in range(m):
  x,y=map(int,input().split())
  adjacent_list[x].append(y)

#print(adjacent_list)

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

def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  res=0
  for j in adjacent_list[i]:
    res=max(res,dfs(j)+1)
  dp[i]=res
  return dp[i]
ans=0
for i in range(1,n+1):
  ans=max(ans,dfs(i))
  
print(ans)

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(100000)
 
N, M = map(int, input().split())
memo = [-1]*N
dic = [[] for i in range(N)]
def dfs(dic, memo, v):
    if memo[v] != -1:
        return memo[v]
    plen = 0
    for i in dic[v]:
        plen = max(plen, dfs(dic, memo, i)+1)
    memo[v] = plen
    return plen
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1].append(y-1)
    
ans = 0
for i in range(N):
    ans = max(ans, dfs(dic, memo, i))
print(ans)

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(100000)
 
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)
dp = [-1] * N
def pathlen(G, dp, v):
    if dp[v] != -1:
        return dp[v]
 
    plen = 0
    for i in G[v]:
        plen = max(plen, pathlen(G, dp, i)+1)
    dp[v] = plen
    return plen
ans = 0
for i in range(N):
    ans = max(ans, pathlen(G, dp, i))
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

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)

dp = [-1] * N
def pathlen(G, dp, v):
    if dp[v] != -1:
        return dp[v]

    plen = 0
    for i in G[v]:
        plen = max(plen, pathlen(G, dp, i)+1)
    dp[v] = plen
    return plen

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

def rec(v):
    global dp, path
    if dp[v] != -1:
        return dp[v]

    res = 0
    for i in path[v]:
        res = max(res, rec(i)+1)

    dp[v] = res
    return res



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

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

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


result = 0
for i in range(N):
    result = max(result, rec(i))

print(result)

Submission status: Accepted

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

memo=[0]*(n+1)
def chain(v):
    if memo[v]!=0:
        return memo[v]
    else:
        for a in l[v]:
            memo[v]=max(chain(a)+1,memo[v])
        return memo[v]
res=0
for i in range(1,n+1):
    res=max(res,chain(i))
print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for _ in range(n)]
deg = [0] * n # 各頂点の入力次数
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)
    deg[y] += 1

from collections import deque
# 入力次数が0の頂点をBFSの開始点とする
q = deque([])
for i in range(n):
    if deg[i] == 0:
        q.append(i)
dp = [0] * n

while q:
    v = q.popleft()

    for nv in G[v]:
        # vからnvへの入力を削除
        deg[nv] -= 1
        if deg[nv] == 0:
            q.append(nv)
            dp[nv] = max(dp[nv], dp[v]+1)
    
print(max(dp))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

dp=[-1]*n  
  
def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp=0
  for nv in g[i]:
    temp=max(temp,dfs(nv)+1)
  dp[i]=temp  
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)

# iを始点としたときの有効パスの最大長さ
dp = [-1] * n
 
def rec(s):
    if dp[s] != -1:
        return dp[s]

    ret = 0
    for ns in G[s]:
        ret = max(ret, rec(ns)+1)
    dp[s] = ret
    return ret

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(20000)

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

def rec_dp(x):
    global dp
    if dp[x] != -1:
        return dp[x]
    else:
        ans = 0
        for y in lst[x]:
            ans = max(ans, rec_dp(y) + 1)
        dp[x] = ans
        return dp[x]
      
dp = [-1] * n
ans = 0
for _ in range(n):
    ans = max(ans, rec_dp(_))
print(ans)

Submission status: Accepted

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

connected=[0]*n
for i in range(n):
    for e in es[i]:
        connected[e]+=1

from collections import deque
que=deque([])
for i in range(n):
    if connected[i]==0:
        que.append(i)
dp=[0]*n

while que:
    s=que.popleft()
    for e in es[s]:
        connected[e]-=1
        dp[e]=max(dp[e], dp[s]+1)
        if connected[e]==0:
            que.append(e)
print(max(dp))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**9)

def dfs(i):
    if distance[i] != -1:
        return distance[i]
    ans = 0
    for node in graph[i]:
        ans = max(ans, dfs(node) + 1)
    distance[i] = ans
    return ans

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

graph = [[] for i in range(n)]
distance = [-1 for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
    
sys.setrecursionlimit(10**9)
    
n, m = map(int, input().split())
adj = defaultdict(list)
radj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    
dp = [-1]*(n+1)

def dfs(e):
    if dp[e] != -1:
        return dp[e]
    
    temp = 0
    for i in adj[e]:
        temp = max(temp, 1+dfs(i))
        
    dp[e] = temp
    return temp
    
    
for i in range(1, n+1):
    dfs(i)
    
print(max(dp))

Submission status: Accepted

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

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

memo = [-1]*n
def dp(v):
    if memo[v] != -1:
        return memo[v]
    res = 0
    for nv in G[v]:
        res = max(res, dp(nv) + 1)
    
    memo[v] = res
    return res

ans = 0
for v in range(n):
    ans = max(ans, dp(v))
print(ans)