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(9**9)
n,m=map(int,input().split())
dp=[0]*n;x=0
s=[set()for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  s[a-1].add(b-1)
def topological_sort(s):
  v,a,b,c=len(s),0,[],[];x=[set()for _ in range(v)]
  for i in range(v):
    for j in s[i]:x[j].add(i)
  for i in range(v):
    l=len(x[i])
    if l==0:a+=1
    b.append([l,i])
  def d(i):
    b[i][0]-=1
    if b[i][0]==0:
      c.append(b[i][1])
      for j in s[b[i][1]]:d(j)
  for i in sorted(b)[:a]:
    c.append(i[1])
    for j in s[i[1]]:d(j)
  return c
for i in topological_sort(s):
  for j in s[i]:dp[j]=max(dp[j],dp[i]+1);x=max(x,dp[j])
print(x)

Submission status: Accepted

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

def dfs(dp,edges,node,visited):
    if node not in visited:
        visited.add(node)
        for kid in edges[node]:
            dfs(dp,edges,kid,visited)
            #print(dp,node,kid)
            dp[node-1] = max(dp[node-1],dp[kid-1])
        if edges[node]:
            dp[node-1] += 1

def solve(edges,n):
    dp = [0]*n
    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            #print(i)
            dfs(dp,edges,i,visited)

    #print(dp)
    print(max(dp))

def main():
    n,m = map(int,input().split())
    edges = {}
    for i in range(1,n+1):
        edges[i] = []

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

    solve(edges,n)


main()

Submission status: Accepted

Solution code:
import sys

def solve():
    n, list_of_xy = read()
    result = think(n, list_of_xy)
    write(result)


def read():
    n, m = read_int(2)
    list_of_xy = []
    for i in range(m):
        list_of_xy.append(read_int(2))
    return n, list_of_xy


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, list_of_xy):
    num_of_input_edges = [0 for _ in range(n + 1)]
    num_of_output_edges = [0 for _ in range(n + 1)]

    linked_list = generate_linked_list(list_of_xy)

    invalid_value = -1
    length_of_longest_path_start_from = [invalid_value for _ in range(n + 1)]

    for x, y in list_of_xy:
        num_of_input_edges[y] += 1
        num_of_output_edges[x] += 1

    for i in range(1, len(num_of_input_edges)):
        if num_of_output_edges[i] == 0:
            length_of_longest_path_start_from[i] = 0

    for i in range(1, len(num_of_input_edges)):
        if num_of_input_edges[i] == 0:
            update_logest_path_start_from(i, linked_list, length_of_longest_path_start_from, invalid_value)

    return max(length_of_longest_path_start_from)


def generate_linked_list(list_of_xy):
    linked_list = {}
    for x, y in list_of_xy:
        if x in linked_list:
            linked_list[x].append(y)
        else:
            linked_list[x] = [y]
    return linked_list


def update_logest_path_start_from(x, linked_list, length_of_longest_path_start_from, invalid_value):
    if length_of_longest_path_start_from[x] != invalid_value:
        return

    dest_from_x = linked_list.get(x, [])
    for y in dest_from_x:
        if length_of_longest_path_start_from[y] == invalid_value:
            update_logest_path_start_from(y, linked_list, length_of_longest_path_start_from, invalid_value)
            length_of_longest_path_start_from[x] = max(length_of_longest_path_start_from[x], length_of_longest_path_start_from[y] + 1)
        else:
            length_of_longest_path_start_from[x] = max(length_of_longest_path_start_from[x], length_of_longest_path_start_from[y] + 1)


def write(result):
    print(result)


if __name__ == '__main__':
    sys.setrecursionlimit(10 ** 5)
    solve()

Submission status: Accepted

Solution code:
from collections import deque

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


queue = deque([])
for i in range(N):
    if node[i][1] == 0:
        queue.append(i)
DP = [0]*N
while queue != deque([]):
    p = queue.popleft()
    for i in node[p][0]:
        node[i][1] -= 1
        DP[i] = max(DP[i],DP[p]+1)
        if node[i][1] == 0:
            queue.append(i)

print(max(DP))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[[] for i in range(n)]
for i in range(m):
    p=[int(j) for j in input().split()]
    l[p[1]-1].append(p[0]-1)

dp=[-1]*n
import sys
sys.setrecursionlimit(10**6)
def f(v):
    if dp[v]!=-1:
        return dp[v]
    p=0
    for i in l[v]:
        p=max(p,f(i)+1)
    dp[v]=p
    return dp[v]

for i in range(n):
    f(i)

print(max(dp))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 * 2)
input = sys.stdin.readline
N, M = map(int, input().split())
Ps = [[] for _ in range(N)]
deg = [0] * N
for i in range(M):
    x, y = map(int, input().split())
    Ps[x - 1].append(y - 1)
    deg[y - 1] += 1

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

dp = [0] * N
while (stack):
    n = stack.pop()
    for p in Ps[n]:
        dp[p] = max(dp[p], dp[n] + 1)
        deg[p] -= 1
        if deg[p] == 0:
            stack.append(p)

print(max(dp))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 * 2)
input = sys.stdin.readline
N, M = map(int, input().split())
Ps = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    Ps[x - 1].append(y - 1)

mem = [-1] * N


def rec(n):
    if mem[n] > -1:
        return mem[n]
    elif len(Ps[n]) == 0:
        mem[n] = 0
        return mem[n]
    else:
        mem[n] = max([rec(Ps[n][i]) for i in range(len(Ps[n]))]) + 1
        return mem[n]


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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 * 2)
N, M = map(int, input().split())
Ps = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    Ps[x - 1].append(y - 1)

mem = [-1] * N


def rec(n):
    if mem[n] > -1:
        return mem[n]
    elif len(Ps[n]) == 0:
        mem[n] = 0
        return mem[n]
    else:
        mem[n] = max([rec(Ps[n][i]) for i in range(len(Ps[n]))]) + 1
        return mem[n]


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

Submission status: Accepted

Solution code:
import collections
n,m = map(int,input().split())
directIn = [set() for _ in range(n+1)]
directOut = [set() for _ in range (n+1)]
value =[0 for _ in range(n+1)]
dq = collections.deque()
for i in range(m):
    a,b = map(int,input().split())
    directOut[a].add(b)
    directIn[b].add(a)
for i in range(1,n+1):
    if not len(directOut[i]):
        dq.append(i)
while len(dq):
    next = dq.popleft()
    for node in directIn[next]:
        directOut[node].remove(next)
        value[node]= max(value[node],value[next]+1)
        if not len(directOut[node]):
            dq.append(node)
print(max(value))

Submission status: Accepted

Solution code:

""""
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""

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

G = []
for _ in xrange(M):
    G.append(map(int, raw_input().split()))

h = [0]*(N+1)

dest = [[] for _ in xrange(N+1)]

for eg in G:
    h[eg[1]]+=1
    dest[eg[0]].append(eg[1])

que = []

for i in xrange(1, N+1):
    if h[i] == 0: que.append(i)

dp = [0]*(N+1)

while len(que)>0:
    now = que.pop(0)
    for edest in dest[now]:
        h[edest]-=1
        if h[edest]==0:
            que.append(edest)
            dp[edest] = max(dp[now] + 1, dp[edest])

print max(dp)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(20000)


def getMax(d, n):
    if len(d[n]) == 0:
        return 0
    if not dp[n] == -1:
      
        return dp[n]
    for k in d[n]:
        dp[n] = max(dp[n], 1 + getMax(d, k))
    return dp[n]


n, m = map(int, input().split())
d = {}
dp = [-1 for _ in range(n + 1)]
for j in range(1, n + 1):
    d[j] = []
for i in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
bs = -1
for i in range(1, n + 1):
    bs = max(bs, getMax(d,i))
print(bs)

Submission status: Accepted

Solution code:
from __future__ import division, print_function
def main():
    n,m=map(int,input().split())
    ## DAG graph , making using dict
    in_degree=[0]*n ## number of incoming edges 
    graph = {} ## graph [ u ] defines edge from u to v
    for i in range(m):
        u, v=map(int,input().split()) 
        if u not in graph:
            graph[u]=[v]
        else :
            graph[u].append(v)
        in_degree[v-1]+=1
    dist=[0]*n
    curr_stack=[] ## starting from nodes with 0 incoming edges
    for i in range(n):
        if in_degree[i]==0:
            curr_stack.append(i+1)
    def dfs (curr_stack):
        while curr_stack:
            u=curr_stack.pop()
            if u not in graph:
                continue
            for item in graph[u]:
                dist[item-1]=max(dist[item-1],dist[u-1]+1)
                in_degree[item-1]-=1
                if in_degree[item-1]==0:
                    curr_stack.append(item)
    dfs(curr_stack)
    print(max(dist))



######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
## DAG graph , making using dict
in_degree=[0]*n ## number of incoming edges 
graph = {} ## graph [ u ] defines edge from u to v
for i in range(m):
    u, v=map(int,input().split()) 
    if u not in graph:
        graph[u]=[v]
    else :
        graph[u].append(v)
    in_degree[v-1]+=1
dist=[0]*n
curr_stack=[] ## starting from nodes with 0 incoming edges
for i in range(n):
    if in_degree[i]==0:
        curr_stack.append(i+1)
def dfs (curr_stack):
    while curr_stack:
        u=curr_stack.pop()
        if u not in graph:
            continue
        for item in graph[u]:
            dist[item-1]=max(dist[item-1],dist[u-1]+1)
            in_degree[item-1]-=1
            if in_degree[item-1]==0:
                curr_stack.append(item)
dfs(curr_stack)
print(max(dist))

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
rev = [list() for _ in range(n+1)]
tr = [0]*(n+1)
ans = [0]*(n+1)
for _ in range(m):
  x,y = map(int,input().split())
  rev[y].append(x)
  tr[x] += 1
q = deque()
for i in range(1,n+1):
  if tr[i] == 0:
    q.append(i)
while q:
  cur = q.popleft()
  for x in rev[cur]:
    tr[x] -= 1
    ans[x] = max(ans[x],ans[cur]+1)
    if tr[x] == 0:
      q.append(x)
print(max(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#dp6 #Longest-Path

import sys
sys.setrecursionlimit(10000000)
def LI(): return list(map(int,sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
def g():
    def dfs(x):
        #既に最長パスがわかっている頂点はそれを返す
        if dp[x] != None:
            return dp[x]
        #移動できる頂点がないとき0
        if len(Graph[x]) == 0:
            dp[x] = 0
            return 0
        else:
            res = 0
            #移動できる頂点の中で最大パスをもつものを探す
            for y in Graph[x]:
                res = max(res,dfs(y)+1)
            dp[x] = res
            return dp[x]

    n,m = LI()
    #dpで各頂点を始点とした最大パスを管理
    dp = [None for _ in range(n)]
    Graph = [[] for _ in range(n)]
    for _ in range(m):
        x,y = LI()
        Graph[x-1].append(y-1)
    #各頂点を始点として最大パスを探す
    for i in range(n):
        dfs(i)
    print(max(dp))
if __name__ == '__main__':
    g()

Submission status: Accepted

Solution code:
import sys
from heapq import *
sys.setrecursionlimit(200000)

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


#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]
dp = [0]*N

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

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

#出力
print(ans)

Submission status: Accepted

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

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

dp = [-1]*N

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

for v in range(N):
    rec(v)

ans = max(dp)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
xy = LIR(M)

utov = [[] for i in range(N+1)]
for x, y in xy:
    utov[x].append(y)

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

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

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

Submission status: Accepted

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

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

dp = [0]*N

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

for v in range(N):
    rec(v)

ans = max(dp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)
hh = [0]*N
for _ in range(M):
    x,y = inpl()
    x,y = x-1, y-1
    lines[x].add(y)
    hh[y] += 1

def TopologicalSort(N,lines,hh):
    q = queue.Queue()
    for t in range(N):
        if hh[t] == 0:
            q.put(t)

    topological = []
    while not q.empty():
        s = q.get()
        topological.append(s)
        for t in lines[s]:
            hh[t] -= 1
            if hh[t] == 0:
                q.put(t)

    return topological

topo = TopologicalSort(N,lines,hh)
dp = [0]*N

for s in topo:
    for t in lines[s]:
        dp[t] = max(dp[t],dp[s]+1)

print(max(dp))

Submission status: Accepted

Solution code:
# @author 

import sys

class GLongestPath:
    def dfs(self, s):
        if self.done[s]:
            return self.dp[s]

        self.done[s] = 1

        ans = 0
        for x in self.adj[s]:
            ans = max(ans, 1 + self.dfs(x))

        self.dp[s] = ans
        return ans

    def solve(self):
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)
        from collections import defaultdict
        n, m = [int(_) for _ in input().split()]
        self.adj = defaultdict(list)
        self.dp = [0] * (n + 1)
        self.done = [0] * (n + 1)
        for i in range(m):
            u, v = [int(_) for _ in input().split()]
            self.adj[u].append(v)

        ans = 0
        for i in range(1, n + 1):
            ans = max(ans, self.dfs(i))

        print(ans)

solver = GLongestPath()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import itertools as ite
import math
import random
import sys

INF = 10 ** 18
MOD = 10 ** 9 + 7

sys.setrecursionlimit(1000000)

N, M = map(int, raw_input().split())
E = [[] for i in range(N + 1)]
for i in range(M):
    x, y = map(int, raw_input().split())
    E[x].append(y)

m = {}
def func(pos):
    if pos in m:
        return m[pos]
    ret = 0
    for to in E[pos]:
        ret = max(ret, func(to) + 1)
    m[pos] = ret
    return ret

print max(func(i) for i in range(1, N + 1))

Submission status: Accepted

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

def rec(i):
    if memo[i] != -1:
        return memo[i]
    elif not graph[i]:
        return 0
    else:
        memo[i] = max([rec(edge) for edge in graph[i]]) + 1
        return memo[i]


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

for i in range(N+1):
    rec(i)

print(max(memo))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6 + 100)
n, m = map(int, input().split())

memo = [-1] * (10 ** 6 + 100)

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

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


def dfs(i):
    if memo[i] != -1:
        return memo[i]
    if not g[i]:
        return 0
    else:
        memo[i] = max(dfs(v) for v in g[i]) + 1
        return memo[i]


for i in range(1, n+1):
    dfs(i)

print(max(memo))

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
N, M = [int(_) for _ in input().split()]

# 隣接関係は隣接リストで管理する
lst_edge = [[] for _ in range(N)]

for _ in range(M):
  # indexを0スタートにする。
  x, y = [int(_)-1 for _ in input().split()] 
  lst_edge[x].append(y)
        
# dp[v] := ノードvを始点とした時の有向パスの長さの最大値
# -1 未訪問で初期化。
dp = [-1] * N

# メモ化再帰
def rec(v):
  # 既に更新済み
  if dp[v] != -1:
    return dp[v]
  ans = 0
  lst_nv = lst_edge[v] # ノードvからいけるノード
  for nv in lst_nv:
    ans = max(ans, rec(nv) + 1) # 一歩進む
  dp[v] = ans # ノードvを始点とした時の有向パスの長さの最大値
  return dp[v]
    
# 全ての点に対して更新する
ans = 0
for v in range(N):
  ans = max(ans, rec(v))
    
print(ans)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
N, M = [int(_) for _ in input().split()]

# 隣接関係は隣接リストで管理する
lst_edge = [[] for _ in range(N)]

for _ in range(M):
  # indexを0スタートにする。
  x, y = [int(_)-1 for _ in input().split()] 
  lst_edge[x].append(y)
        
# 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 = max(ans, rec(nv) + 1)
  dp[v] = ans
  return dp[v]
    
# 全ての点に対して更新する
ans = 0
for v in range(N):
  ans = max(ans, rec(v))
    
print(ans)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
N, M = [int(_) for _ in 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 = max(ans, rec(nv) + 1)
  dp[v] = ans
  return dp[v]
    
# 全ての点に対して更新する
ans = 0
for v in range(N):
  ans = max(ans, rec(v))
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
to_y = [[] for _ in range(N)]
deg = [0] * N
stack = []
dp = [0] * N

for _ in range(M):
	x, y = map(int, input().split())
	to_y[x - 1].append(y - 1)
	deg[y - 1] += 1
	
for i in range(N):
	if deg[i] == 0:
		stack.append(i)
		
while stack:
	x = stack.pop(-1)
	for y in to_y[x]:
		dp[y] = max(dp[y], dp[x] + 1)
		deg[y] -= 1
		if deg[y] == 0:
			stack.append(y)
			
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 5)
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
x, y = [0] * M, [0] * M
from_x = [[] for _ in range(N)]
memo = [-1] * N
ans = 0

def length(i):
	if memo[i] >= 0:
		return memo[i]
	else:
		if len(from_x[i]) == 0:
			memo[i] = 0
			return memo[i]
		else:
			ret = 0
			
			for j in from_x[i]:
				tmp = length(j) + 1
				if tmp > ret:
					ret = tmp
					
			memo[i] = ret
			return ret

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

for i in range(N):
	tmp = length(i)
	if tmp > ans:
		ans = tmp

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())

d = defaultdict(lambda:[])

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

dp = [-1]*N

def dist(s):
    if dp[s] >= 0:
        return dp[s]
    if d[s] == []:
        dp[s] = 0
        return 0
    res = 0
    for t in d[s]:
        res = max(res,1+dist(t))
    dp[s] = res
    return res

ans = 0
for i in range(N):
    ans = max(ans,dist(i))

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
revg = [[] for _ in range(n)]
ins = [0] * n
for i in range(m):
    x, y = map(int, input().split())
    g[x - 1].append(y - 1)
    revg[y - 1].append(x - 1)
    ins[y - 1] += 1
tl = []
q = deque(v1 for v1 in range(n) if ins[v1] == 0)
while q:
    v1 = q.popleft()
    tl.append(v1)
    for v2 in g[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
dp = [0] * n
for p in tl:
    for node in revg[p]:
        dp[p] = max(dp[p], dp[node] + 1)
print(max(dp))

Submission status: Accepted

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

def LI(): return [int(x) for x in input().split()]
def TI(): return tuple(LI())
def II(): return int(input())

N,M=LI()

MP={}
for _ in range(M):
    fr, to = TI()
    if not fr in MP:
        MP[fr] = []
    MP[fr].append(to)

RESL=[-1]*(N+1)
def dfs(n):
    if RESL[n] != -1:
        return RESL[n]
    else:
        res = 0
        if n in MP:
            for to in MP[n]:
                res = max(res, dfs(to))
            res += 1
        RESL[n] = res
        return res
for i in range(1, N+1): dfs(i)
# print(RESL)
print(max(RESL))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
# 向かう先
outs = [[] for _ in range(n + 1)]
# 向かわれる数
ins = [0] * (n + 1)
for _ in range(m):
    x, y = map(int, input().split())
    outs[x].append(y)
    ins[y] += 1
queue = [i for i in range(1, n + 1) if ins[i] == 0]

l = []

while queue:
    s = queue.pop()
    l.append(s)
    for r in outs[s]:
        ins[r] -= 1
        if ins[r] == 0:
            queue.append(r)


dp = [0] * (n + 1)
for v in l:
    d = dp[v] + 1
    for k in outs[v]:
        dp[k] = max(dp[k], d)
print(max(dp))

Submission status: Accepted

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

sys.setrecursionlimit(10**5+1)
dp = [-1]*(N+1)
def distance(start):
    if dp[start] > 0:
        return dp[start]
    elif len(edge[start]) == 0:
        dp[start] = 0
        return 0
    else:
        temp = [distance(e) + 1 for e in edge[start]]
        dp[start] =  max(temp)
        return dp[start]

for i in range(1,N+1):
    go = distance(i)
print(max(dp))

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N + 1)]
    D = [0] * (N + 1)
    for _ in range(M):
        x, y = map(int, input().split())
        E[x].append(y)
        # Keeps number of input destinations for each output distination.
        D[y] += 1

    # topological sort
    Q = [i for i in range(1, N + 1) if D[i] == 0]
    L = []
    while Q:
        s = Q.pop()
        L.append(s)
        for r in E[s]:
            D[r] -= 1
            if D[r] == 0:
                Q.append(r)

    dp = [0] * (N + 1)
    for v in L:
        d = dp[v] + 1
        for k in E[v]:
            dp[k] = max(dp[k], d)
    print(max(dp))


main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    D = [0] * (N)
    for _ in range(M):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        E[x].append(y)
        # Keeps number of input destinations for each output distination.
        D[y] += 1

    # topological sort
    Q = [i for i in range(N) if D[i] == 0]
    L = []
    while Q:
        s = Q.pop()
        L.append(s)
        for r in E[s]:
            D[r] -= 1
            if D[r] == 0:
                Q.append(r)

    dp = [0] * N
    for v in L:
        for k in E[v]:
            dp[k] = max(dp[k], dp[v] + 1)
    print(max(dp))


main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N + 1)]
    D = [0] * (N + 1)
    for _ in range(M):
        x, y = map(int, input().split())
        E[x].append(y)
        # Keeps number of input destinations for each output distination.
        D[y] += 1

    # topological sort
    Q = [i for i in range(1, N + 1) if D[i] == 0]
    L = []
    while Q:
        s = Q.pop()
        L.append(s)
        for r in E[s]:
            D[r] -= 1
            if D[r] == 0:
                Q.append(r)

    dp = [0] * (N + 1)
    for v in L:
        for k in E[v]:
            dp[k] = max(dp[k], dp[v] + 1)
    print(max(dp))


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300*300*300+10)

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


N, M = map(int, input().split())
G = [[int(_) for _ in input().split()] for _ in range(M)]
dp = [-1]*(N)
Graph = [[] for _ in range(N)]
ans = 0

for i in G:
    Graph[i[0]-1].append(i[1]-1)

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

print(ans)