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:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))


def topological_sort(g):
    result = []
    status = [0] * len(g)

    def _dfs(v):
        st = [v]
        while 0 < len(st):
            cv = st[-1]
            if status[cv] == 0:
                status[cv] = 1
                for _, d, _ in g.edges(cv):
                    if status[d] == 1:
                        raise ValueError('has cyclic')
                    st.append(d)
            elif status[cv] == 1:
                status[cv] = 2
                result.append(cv)
            if status[cv] == 2:
                st.pop()

    for v in range(len(g)):
        _dfs(v)
    return list(reversed(result))


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    es = [(xx-1, yy-1, 0) for xx, yy in zip(x,y)]
    g = DGraph(N, es)

    order = topological_sort(g)
    dp = [0] * N
    for i in order:
        for _, j, _ in g.edges(i):
            dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

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))
    result = solve(N, M, x, y)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fileinput
from collections import defaultdict

def longest_path(node_count, edges):
    graph = defaultdict(list)
    for v_a, v_b in edges:
        graph[v_a].append(v_b)
    
    visited_nodes = [False] * (node_count + 1)
    sorted_nodes = []

    node_stack = []
    for node in graph:
        if visited_nodes[node]:
            continue

        node_stack.append([node, 0])
        visited_nodes[node] = True
        while node_stack:
            top_node, last_child = node_stack[-1]
            if top_node in graph and last_child < len(graph[top_node]):
                node_stack[-1][1] += 1
                current_child = graph[top_node][last_child]
                if not visited_nodes[current_child]:
                    node_stack.append([current_child, 0])
                    visited_nodes[current_child] = True
            else:
                node_stack.pop()
                sorted_nodes.append(top_node)
    
    path_table = {}
    longest_path = 0
    for node in sorted_nodes:
        if node in graph:
            path_table[node] = max(
                path_table[n] for n in graph[node]
            ) + 1
        else:
            path_table[node] = 0
        longest_path = max(path_table[node], longest_path)        

    return longest_path

inp = fileinput.FileInput()

split = inp.readline().split(" ")
node_count = int(split[0])
edge_count = int(split[1])
edges = []

for _ in range(edge_count):
    split = inp.readline().split(" ")
    edges.append(
        (int(split[0]), int(split[1]))
    )

print(longest_path(node_count, edges))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for i in range(1+n)]
dist=[-1]*(1+n)
for i in range(m):
    a,b=map(int,input().split())
    g[a].append(b)
    
def dfs(cur):
    if dist[cur]!=-1:
        return dist[cur]
        
    if not g[cur]:
        dist[cur]=0
    else:
        dist[cur]=1+max([dfs(nb) for nb in g[cur]])
    return dist[cur]

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def topological_sort(V, E):
    '''
    Kahn's Algorithm (O(|V| + |E|) time)
    Input:
        V = [0, 1, ..., N-1]: a list of vertices of the digraph
        E: the adjacency list of the digraph (dict)
    Output:
        If the input digraph is acyclic, then return a topological sorting of the digraph.
        Else, return None.
    '''
    indeg = {v: 0 for v in V}
    for ends in E.values():
        for v in ends:
            indeg[v] += 1
    
    q = deque([v for v in V if indeg[v] == 0])
    top_sorted = []
    while q:
        v = q.popleft()
        top_sorted.append(v)
        
        for u in E[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    if len(top_sorted) == len(V): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        return None

N, M = map(int, input().split())
V = list(range(1, N+1))
E = {v: [] for v in V}
for _ in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
ts = topological_sort(V, E)
dp = {v: 0 for v in V}
for v in reversed(ts):
    dp[v] = max([dp[u] + 1 for u in E[v]]) if E[v] else 0
print(max(dp.values()))

Submission status: Accepted

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

def get_inputs():
    N, M = map(int, input().split())
    
    # グラフgを初期化
    g = [[] for _ in range(N)]
    
    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)
    
    return N, M, g


def getlp(x):
    global dp, g
    
    if dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        dp[x] = max([getlp(y) for y in g[x]]) + 1
        return dp[x]


N, M, g = get_inputs()

dp = [-1] * N
ans = 0
for x in range(N):
    ans = max(ans, getlp(x))

print(ans)

Submission status: Accepted

Solution code:
import sys

def topological_sort(E, D):
    n = len(E)
    Q = [i for i in range(n) if D[i] == 0]
    L = []
    while Q:
        p = Q.pop()
        L.append(p)
        for vf in E[p]:
            D[vf] -= 1
            if not D[vf]:
                Q.append(vf)
    
    if len(L) != n:
        return False
    return L

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(M):
    x, y = map(int, sys.stdin.readline().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    Dim[y] += 1

dp = [0]*N

for v in topological_sort(Edge, Dim):
    d = dp[v] + 1
    for vf in Edge[v]:
        dp[vf] = max(dp[vf], d)

print(max(dp))

Submission status: Accepted

Solution code:
import sys


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

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]
start_point = [True] * n
for i in range(m):
    tree[info[i][0] - 1].append(info[i][1] - 1)
    start_point[info[i][1] - 1] = False
     
dp = [-1]*n

def dfs(pos):
    if dp[pos] !=-1:
        return dp[pos]
    if not tree[pos]:
        dp[pos] = 0
        return 0
    ans = 0
    for i in tree[pos]:
        ans = max(ans, dfs(i) + 1)
    dp[pos] = ans
    return ans

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)

n,m = [int(i) for i in input().split()]

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

memo = [-1]*n

def longest(v): #nを終点とするlongest
    if memo[v] >= 0:
        return memo[v]
    else:
        c=0
        for j in oya[v]:
            c = max(c,longest(j)+1)
        memo[v] = c
        return c

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

print(max(memo))    
#print(memo)

Submission status: Accepted

Solution code:
def g():
    from collections import defaultdict
    import sys

    sys.setrecursionlimit(10 ** 6)
    N, M = map(int, input().split())
    xy = defaultdict(list)
    memo = {}
    for _ in range(M):
        x, y = map(int, input().split())
        xy[x].append(y)

    def g2(x):
        if x in memo:
            return memo[x]
        else:
            r = 0
            for ny in xy[x]:
                r = max(r, g2(ny) + 1)
            memo[x] = r
        return r

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


if __name__ == '__main__':
    ans = g()
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)


def rec(node):
    if memo[node]:
        return memo[node]

    res = 0
    for next_node in edge[node]:
        res = max(res, rec(next_node) + 1)

    memo[node] = res
    return res


n, m = map(int, input().split())
memo = [0] * (n + 1)
edge = defaultdict(list)

for i in range(m):
    x, y = map(int, input().split())
    edge[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)

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

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

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if not V[x]:
        dp[x] = 0
        return 0
    l = max(dfs(v) for v in V[x]) + 1
    dp[x] = l
    return l

print(max(dfs(v) for v in range(N)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g_o = [[] for x in range(n)]
g_i = [0] * n
for _ in range(m):
    p, c = map(int, input().split())
    g_o[p - 1].append(c - 1)
    g_i[c - 1] += 1
sor = [e for e in range(n) if g_i[e] == 0]
for node in sor:
    for i in g_o[node]:
        g_i[i] -= 1
        if g_i[i] == 0:
            sor.append(i)
dp = [0] * n
for node in sor:
    for c in g_o[node]:
        if dp[c] < dp[node] + 1:
            dp[c] = dp[node] + 1
print(max(dp))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g_o = [[] for x in range(n)]
g_i = [0] * n
for _ in range(m):
    p, c = map(int, input().split())
    g_o[p - 1].append(c - 1)
    g_i[c - 1] += 1
get_root = lambda g: [e for e in range(n) if g[e] == 0]
sor = get_root(g_i)
for node in sor:
    for i in g_o[node]:
        g_i[i] -= 1
        if g_i[i] == 0:
            sor.append(i)
dp = [0] * n
for node in sor:
    for c in g_o[node]:
        if dp[c] < dp[node] + 1:
            dp[c] = dp[node] + 1
print(max(dp))

Submission status: Accepted

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

from collections import deque

que =deque()
for i in range(n):
    if deg[i] == 0:
        que.append(i)
dp = [0] *n

while que:
    v = que.popleft()
    nv = edge[v]
    for nv in nv:
        deg[nv] -=1
        if deg[nv] ==0:
            que.append(nv)
            dp[nv] = max(dp[v] + 1 ,dp[nv])
print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque
n, e = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
source_num = [0] * n
distance = [0] * n
for i in range(e):
    f, t = map(int, input().split())
    f -= 1
    t -= 1
    source_num[t] += 1
    edge[f].append(t)

dq = deque()
for i, item in enumerate(source_num):
    if item == 0:
        dq.append(i)
        source_num[i] = -1
while(dq):
    i = dq.pop()
    source_num[i] = -1
    for v in edge[i]:
        distance[v] = max(distance[v], distance[i] + 1)
        source_num[v] -= 1
        if source_num[v] == 0:
            dq.append(v)
print(max(distance))

Submission status: Accepted

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

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

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

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

dp = [-1] * N
length = [0] * N

def cnt(j):
    if dp[j] != -1:
        return(dp[j])
    else:
        dp[j] = 0
        for k in graph[j]:
            dp[j] = max(cnt(k)+1, dp[j])
        return dp[j]

for i in range(N):
    length[i] = cnt(i)

print(max(length))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


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


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

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

dp = [-1] * N

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

Submission status: Accepted

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

N, M = map(int, input().split())
        
G = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    
dp = [-1] * (N)

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def sub():

    N, M = [int(e) for e in input().split()]
    es = [[int(x) for x in input().split()] for _ in range(M)]

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

    q = deque(v1 for v1 in range(1, N+1) if ins[v1] == 0)
    dp_table = [0 for i in range(N+1)]
    res = []
    while q:
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)
                dp_table[v2] = max(dp_table[v2], dp_table[v1] + 1)
    print(max(dp_table))

if __name__ == "__main__":
    sub()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def MI(): return map(int, input().split())


def LI_(): return [int(x) - 1 for x in input().split()]


def main():
    import sys
    sys.setrecursionlimit(5*(10**5))
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y = LI_()
        edge[x].append(y)

    def go_to_leaf(n):
        if dp[n] >= 0:
            return dp[n]
        ret = 0
        for y in edge[n]:
            ret = max(go_to_leaf(y) + 1, ret)
        dp[n] = ret
        return ret

    dp = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, go_to_leaf(i))
    print(ans)

    """start = 0
    while rev_edge[start]:
        start = rev_edge[start][0]
    stack = set([start])
    ans = 0
    for _ in range(N + 1):
        tmp = []
        print(stack)
        while stack:
            now = stack.pop()
            tmp.extend(edge[now])
        if not tmp:
            print(tmp)
            break
        stack = set(tmp)
        ans += 1
    print(ans)"""


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def get_nagasa(i):
    if nagasa[i] != -1:
        return nagasa[i]
    if ko[i] == []:
        nagasa[i] = 0
        return 0
    re = 0
    for ii in ko[i]:
        p = get_nagasa(ii) + 1
        if p > re:
            re = p
    nagasa[i] = re
    return re

n, m = map(int, input().split())
ko = [[] for _ in range(n)]
nagasa = [-1] * n
for _ in range(m):
    x, y = map(int, input().split())
    ko[x - 1] += [y - 1]
mx = 0
for i in range(n):
    tmp = get_nagasa(i)
    if tmp > mx:
        mx = tmp
print(mx)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# TLE
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n):
    # print('Search Start: ' + str(n))
    if checked[n]:
        # print('Checked: ' + str(n))
        return path_len[n]
    # print(graph)
    stack = graph[n]
    y = 0
    while stack:
        x = stack.pop()
        y = max(y, 1 + dfs(x))
    checked[n] = True
    if path_len[n] <= y:
        path_len[n] = y
    # print('Search End: ' + str(n))
    # print(path_len)
    return y

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

graph = {i: deque() for i in range(N)}
checked = [False for _ in range(N)]
path_len = [0 for _ in range(N)]

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

for i in range(N):
    if checked[i]:
        continue
    dfs(i)

print(max(path_len))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
edge = [[] for i in range(n)]
st = []
to = [0]*n
dp = [0]*n
for i in range(m):
  x,y = map(int,input().split())
  edge[x-1].append(y-1)
  to[y-1] += 1
for i in range(n):
  if to[i] == 0:
    st.append(i)
while len(st) > 0:
  go = st.pop()
  for i in edge[go]:
    to[i] -= 1
    if to[i] == 0:
      st.append(i)
    dp[i] = max(dp[go]+1,dp[i])
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
childs = [[] for _ in range(N)]
for i in range(M):
    p, c = map(int, input().split())
    childs[p-1].append(c-1)

depth = [-1] * N
def dfs(n):
    if depth[n] != -1:
        return depth[n]
    if childs[n]:
        depth[n] = max((dfs(nc) for nc in childs[n])) + 1
    else:
        depth[n] = 0
    return depth[n]

print(max((dfs(n) for n in range(N))))

Submission status: Accepted

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

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

dp = [-1] * n
def count(a):
    if dp[a] != -1:
        return dp[a]
    else:
        dp[a] = 0
        for i in graph[a]:
            dp[a] = max(count(i) + 1, dp[a])
        return dp[a]

print(max([count(i) for i in range(n)]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(int(1e5))

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

g = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().rstrip().split(' '))
    g[y-1].append(x-1)
    
dp = [-1] * N
def rec(v):
    if dp[v] != -1:
        return dp[v]
        
    count = 0
    for x in g[v]:
        count = max(count, rec(x)+1)
        
    dp[v] = count
    
    return count
   
for i in range(N):
    rec(i)

print(max(dp))

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int, input().split())
to_nodes = [[] for _ in range(N)] #終点ノード
deg = [0]*N #入力辺

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

st = deque()
push, pop = st.append, st.popleft

for n in range(N):
    if deg[n] == 0:
        push(n) #入力辺が無く、最長パスの始点になりうる点を取得

dp = [0]*N
#print(deg,dp)
while st:
    n = pop()
    nodes = to_nodes[n]
    for ni in nodes:
        deg[ni] -= 1 #使ったエッジをグラフから削除する
        if deg[ni] == 0:
            push(ni)
            dp[ni] = max(dp[ni], dp[n] + 1)
        #print('n',n,'ni',ni,deg,dp)

print(max(dp))

'''''
@input
4 5
1 2
1 3
3 2
2 4
3 4
@output
[0, 2, 1, 2] [0, 0, 0, 0]
n 0 ni 1 [0, 1, 1, 2] [0, 0, 0, 0]
n 0 ni 2 [0, 1, 0, 2] [0, 0, 1, 0]
n 2 ni 1 [0, 0, 0, 2] [0, 2, 1, 0]
n 2 ni 3 [0, 0, 0, 1] [0, 2, 1, 0]
n 1 ni 3 [0, 0, 0, 0] [0, 2, 1, 3]
3
'''''

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.appendleft(i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    # 頂点iにたどり着くまでの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for _ in range(M):
        x, v = list(map(int, stdin.readline().rstrip().split()))
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = deque([])

    is_visited = [False] * (N+1)

    # トポロジカルソートの実行
    tsort()


    for x in tsort_res:
        for v in nextl[x]:
            dp[v] = max(dp[v], dp[x] + 1)

    # for DEBUG
    #print(dp)
    print(max(dp))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.appendleft(i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for _ in range(M):
        x, v = list(map(int, stdin.readline().rstrip().split()))
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = deque([])

    is_visited = [False] * (N+1)

    # トポロジカルソートの実行
    tsort()

    # 今回は逆順に使うのでリバースする
    # つまり、トポロジカルオーダーの最後の番号に該当する頂点から処理を行う
    # 汎用性のため、dfsでは先頭に追加するようにしている
    #tsort_res = list(tsort_res)[::-1]

    """
    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)
    """
    for x in tsort_res:
        for v in nextl[x]:
            dp[v] = max(dp[v], dp[x] + 1)


    # for DEBUG
    #print(dp)
    print(max(dp))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import sys

# 再起の上限を変更
sys.setrecursionlimit(100000)

INF = 10 ** 10

# 深さ優先探索
def dfs(i):
    global is_visited
    global tsort_res

    if is_visited[i]:
        return 

    is_visited[i] = True
    for j in nextl[i]:
        dfs(j)
    
    # 帰りがけ順で追加
    # 追加は先頭に行う
    tsort_res.appendleft(i)


# トポロジカルソート
def tsort():
    for i in range(1, N+1):
        dfs(i)

if __name__ == "__main__":

    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    # トポロジカルソートで頂点iより後ろのパスの最大長
    dp = [0] * (N+1)

    # 頂点xから頂点vへの有向辺
    nextl = [[] for _ in range(N+1)]
    for _ in range(M):
        x, v = list(map(int, stdin.readline().rstrip().split()))
        nextl[x].append(v)
    
    # トポロジカルソートされた結果の入るリスト
    tsort_res = deque([])

    is_visited = [False] * (N+1)

    tsort()

    # 今回は逆順に使うのでリバースする
    # 汎用性のため、dfsでは先頭に追加するようにしている
    tsort_res = list(tsort_res)[::-1]

    for x in tsort_res:
        for v in nextl[x]:
            dp[x] = max(dp[x], dp[v] + 1)


    # for DEBUG
    #print(dp)
    print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)


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

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

x_to_y = defaultdict(list)
for x, y in XY:
    x_to_y[x].append(y)


@lru_cache(N)
def depth(n):
    ret = -1
    for y in x_to_y[n]:
        ret = max(ret, depth(y))
    return ret + 1


        
depths = [depth(n) for n in range(1, N + 1)]
print(max(depths))

Submission status: Accepted

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_g

G - Longest path

"""
import collections
import functools
import sys
sys.setrecursionlimit(1000000)


def get_adj_list(pairs):
    adj = collections.defaultdict(list)
    for (i, j) in pairs:
        adj[i].append(j)
    return adj


def solve(pairs):
    adj_list = get_adj_list(pairs)

    @functools.lru_cache(1000000)
    def dfs(u):
        res = -1
        for v in adj_list[u]:
            res = max(res, dfs(v))
        return 1 + res

    # depths = [dfs(u) for u in range(1, N+1)]
    # print(depths)
    depths = (dfs(u) for u in range(1, N+1))
    return max(depths, default=0)


N, M = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(M)]
res = solve(pairs)
print(res)

Submission status: Accepted

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

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

dp = [None] * (N+1)

def get_dp(i):
    if dp[i] != None:
        return dp[i]
    yListSub = yList[i]
    if yListSub == []:
        dp[i] = 0
        return 0
    else:
        dp[i] = 1+ max(map(get_dp,yListSub))
        return dp[i]

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

[get_dp(i) for i in range(0,N+1)]
print(max(dp))

Submission status: Accepted

Solution code:
import sys

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


def get_kyori(i):
    if kos[i] == []:
        kyori[i] = 0
        return 0
    if kyori[i] > -1:
        return kyori[i]
    re = 0
    for ko in kos[i]:
        new = get_kyori(ko) + 1
        if re < new:
            re = new
    kyori[i] = re
    return re


n, m = map(int, input().split())
kos = [[] for _ in range(n + 1)]
kyori = [-1] * (n + 1)
for _ in range(m):
    oya, ko = map(int, input().split())
    kos[oya] += [ko]

for i in range(1, n + 1):
    if kyori[i] == -1:
        kyori[i] = get_kyori(i)

print(max(kyori[1:]))

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    G[x-1].add(y-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
dp=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    v=res[i]
    for p in G[v]:
        dp[v]=max(dp[v],dp[p]+1)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)
d = [-1] * N


def dfs(u):
    if d[u] != -1:
        return d[u]

    ma = 0
    for w in G[u]:
        ma = max(ma, dfs(w))

    d[u] = ma + 1
    return ma + 1


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

print(ans - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys

MEMO = dict()

def search(n, data):
    global MEMO

    if n in MEMO:
        return MEMO[n]
    else:
        if not n in data:
            MEMO[n] = 0
            return 0

        MEMO[n] = max(search(i, data) for i in data[n]) + 1
        return MEMO[n]


def main():
    # sys.setrecursionlimit(65535)
    sys.setrecursionlimit(10**9)
    N, M = map(int, input().split())
    data = dict()
    for _ in range(M):
        x, y = map(int, input().split())
        if x not in data:
            data[x] = [y]
        else:
            data[x].append(y)

    print(max(search(n, data) for n in range(1, N+1)))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

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

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    return b

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

    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] = chmax(dp[nv], dp[v] + 1)

    print(max(dp))

main()

Submission status: Accepted

Solution code:
import sys
import collections

# 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)]
    # 各頂点の入力辺の本数
    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  

    while len(que) > 0:
        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] = chmax(dp[nv], dp[v] + 1)
    
    print(max(dp))


main()